Vagrant and VirtualBox gurumeditation problem

This is related to this question: https://www.digitalocean.com/community/questions/install-vagrant-on-ubuntu-12-04

The above question did not receive any answer that was accepted, or indeed helpful. I’ve been at it for two days.

In summary, I create an Ubuntu droplet (tried both 12.04 and 14.04), I install VirtualBox and Vagrant (I’ve tried both apt-get versions and versions directly from Oracle and VagrantUp in all combinations). Then I add a box to vagrant (I’ve tried 7 different boxes, both 32 and 64 bit), and vagrant up. Once I do that, I get

<pre> The guest machine entered an invalid state while waiting for it to boot. Valid states are ‘starting, running’. The machine is in the ‘gurumeditation’ state. Please verify everything is configured properly and try again.

If the provider you’re using has a GUI that comes with it, it is often helpful to open that and watch the machine, since the GUI often has more helpful error messages than Vagrant can retrieve. For example, if you’re using VirtualBox, run vagrant up while the VirtualBox GUI is open. </pre>

From the logs, VirtualBox exits with error 4005 (whatever that means).

Any help is much appreciated.