On Ubuntu 16.04 make sure to uninstall any previous versions of virtualbox:

sudo apt-get purge virtualbox virtualbox-dkms virtualbox

The reinstall virtualbox as downloaded from virtualbox.org

sudo dpkg -i Downloads/virtualbox-5.1_5.1.22-115126-Ubuntu-xenial_amd64.deb

This fixed the error for me.

It has to help:

sudo /sbin/vboxconfig

Then launch your virtual machine.It helped me ;-)

Important pre-amble:

Please note that I wrote this answer back in 2015/2016 and targeted VirtualBox and Vagrant and Ubuntu headless 14.04.

Your mileage may vary after a while.

If you have a similar problem but for a different version, feel free to edit this answer and append your answer above my answer for Ubuntu 14.04 Let's help everyone to progress together.

I myself will do the same and update this answer for newer versions when I start to use them.

Answers:

Ubuntu 14.04 Headless with Vagrant and VirtualBox

I found this page when I had the same issue.

Now I have solved mine. I hope that my solution can help you.

Download the latest AMD64 for virtualbox and install

1. Go https://www.virtualbox.org/wiki/Linux_Downloads
2. Choose the AMD64 which is a deb because I am trying to run vagrant on a 64 bit Ubuntu 14.04 server 64-bit edition (My original problem was that I had used the i386)
3. Then as root, dpkg -i whatever_is_the_latest_version_virtualbox.deb
4. apt-get -f install This will install the dependencies

Download the latest AMD64 for vagrant and install

1. Go https://www.vagrantup.com/downloads.html
2. Choose Debian 64 bit
3. Then as root, dpkg -i whatever_is_the_latest_version_vagrant.deb
4. apt-get -f install This will install the dependencies

Then do the rest of your vagrant box setup.

It should work now.