I had the same issue, but none of other answers fully solved my problem. Answer by @Kiee was helpful, although all I could see in the GUI was a black screen (with underscore in top-left, this issue in Virtual Box also has been raised separately in stack overflow, again nothing helped).
Eventually, a solution proved to be very simple: check version of your virtual machine.
More precisely, I had a box from someone else with 64-bit Debian, but Virtual Box insisted to treat it as 32-bit, what I didn't notice. To change it, open Virtual Box, then open terminal and run
vagrant up
wait for the line
default: SSH auth method: private key
now you can hit ctrl+C (or wait for timeout) and run
vagrant halt
your virtual machine won't be destroyed, so you can see it in the menu of Virtual Box, but will be powered off, so you can change settings. Chose your machine in the menu, click 'Settings'->'General' and chose proper 'Version', for me it was 'Debian (64-bit)'. After this type vagrant up
again.
If this is a case for you (or different changes in 'Settings' solved your issue), you can create new box from the repaired one typing
vagrant package --output mynew.box
Some more details: host 32-bit Ubuntu 12.04, guest 64-bit Debian 8.1, Virtual Box 5.0.14, Vagrant 1.8.1