Ran into the same problem on Linux after running rails new, what fixed it was installing libyaml-devel with the distro's package manager.