Sometimes it happens that vagrant hangs during boot of your virtual image. Right after typing:

$ vagrant up

It hangs for a long time and then finally throws:

[default] Failed to connect to VM!
Failed to connect to VM via SSH. Please verify the VM successfully booted
by looking at the VirtualBox GUI.

If you open VirtualBox you'll see that the virtual machine preview shows a black screen with kernels to choose from. This is GRUB requiring user input to boot further.

Here's how to fix that.

First, get the machine id

$ # Before v1.1
$ # MACHINE_ID=$(awk -F\" '{print $6}' .vagrant)
$ # After v1.1
$ MACHINE_ID=$(cat .vagrant/machines/default/virtualbox/id)

Power off the VM

$ VBoxManage controlvm ${MACHINE_ID} poweroff

Then boot the machine with a GUI console

$ VBoxManage startvm ${MACHINE_ID}

Wait for it to boot, login, run:

$ sudo update-grub

When successful, shut it down

$ VBoxManage controlvm ${MACHINE_ID} poweroff

And after this, vagrant up will just boot your VM normally :)