I'm trying to install the Guest Additions in VirtualBox 4.04. Host OS is Ubuntu desktop 11.04 64bit, guest OS is Ubuntu server 11.10 64bit.

$ sudo ./VBoxLinuxAdditions.run

After some output this line is printed:

The headers for the current running kernel were not found.

But the headers are installed, at least accordingly to dpkg:

$ dpkg --get-selections | grep linux-headers
linux-headers-3.0.0-12            install
linux-headers-3.0.0-12-server     install
linux-headers-server              install

The running kernel is:

$ uname -a
Linux foobar 3.0.0-12-server #20-Ubuntu SMP Fri Oct 7 16:36:30 UTC 2011 x86_64 x86_64 X86_64 GNU/Linux

How do I fix things so that Guest Additions installer is able to find kernel headers?

Update: added full output.

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

Building the main Guest Additions module ...done.
Building the shared folder support module ...fail!
(Look at /var/log/vboxadd-install.log to find out what went wrong)
Installing the Window System drivers ...fails!
(Could not find the X.Org or XFree86 Window System).

I don't care for fail #2, because that's a server and I don't need X server. But I need shared folder support.

Some further detail:

$ tail /val/log/vboxadd-install.log
..........
cc1: some warnings being treated as errors
make[2]: *** [/tmp/vbox.0/vfsmod.o] Error 1
make[1]: *** [_module_/tmp/vbox.0] Error 2
make: *** [vboxsf] Error 2