I had this problem and followed, quite blindly, all steps. Tha last step is, purge VirtualBox and install it again. Here comes my doubt as I have a few virtual machines configured and I don't want to loose any information. Will these machines be there after this?:
sudo apt-get purge virtualbox
sudo apt-get install virtualbox
Thanks
your kernel headers cannot be found
so I had to install headers withsudo apt-get install linux-headers-$(uname -r)
– K. Weber Mar 18 '16 at 15:36