Error: kernel headers not found. (But they are in place)

The message is misleading.

In my case it was actually missing dkms so before you install the addition run

sudo apt-get install build-essential linux-headers-`uname -r` dkms

(Even though this question has an accepted answer, I'm adding this answer in case it helps somebody else out...)

Although I had identical symptoms, I tried out every suggestion to this question, and yet nothing worked. I finally found this thread suggesting it's the VirtualBox version not being up to date with the Linux kernel version.

So, if nothing works for you, try installing the latest version from: http://download.virtualbox.org/virtualbox/ (at time of writing, this was 4.2.6 for Debian-based systems).

I fixed this error by installing dkms and upgrading my version of VirtualBox. Turns out old versions of the VirtualBox guest additions often won't work with the latest kernels.