Some Vagrant baseboxes (like Opscode's bento boxes) ship with stale apt package indexes. When you run vagrant up and your main provisioner tries to install a package, you get an error. Here's a quickfix that takes advantage of Vagrant's support for multiple provisioners:
config.vm.provision :shell do |shell|
shell.inline = 'test -f $1 || (sudo apt-get update -y && touch $1)'
shell.args = '/var/run/apt-get-update'
end