Eu tive o mesmo problema com o Ubuntu 12.10 e encontrei uma solução. Basta adicionar essas linhas ao seu Vagrantfile:
config.vm.customize ["modifyvm", :id, "--natdnshostresolver1", "on"]
config.vm.customize ["modifyvm", :id, "--natdnsproxy1", "on"]
Para o Vagrant 1.1+ você precisará (graças a farooqsadiq)
config.vm.provider "virtualbox" do |v|
v.customize ["modifyvm", :id, "--natdnshostresolver1", "on"]
end
Parece ser um bug conhecido no VirtualBox no Ubuntu 12.10: