Guest Additions install fail on VirtualBox

Problem

You have a Ubuntu guest virtual machine running on VirtualBox that is running on a Ubuntu host OS. You try to install Guest Additions and it fails.

The headers for the current running kernel were not found. If the following
module compilation fails then this could be the reason.

Building the main Guest Additions module ...fail!
(Look at /var/log/vboxadd-install.log to find out what went wrong)

Solution

Though the error looks like it has something to do with the kernel, the actual solution turned out to be quite basic. My Ubuntu host OS was 12.04 and it was running VirtualBox 4.1.2. Now the guest OS was Ubuntu 13.10, which is much newer. The problem turned out to be that the Guest Additions, which comes from VirtualBox, was much older than the guest OS. I uninstalled the old Virtual Box and installed the latest VirtualBox 4.3.8 from the web and Guest Additions worked fine!