I've installed the guest additions on my Debian Linux virtual machine. Installation went through without any problems.
For some reason I still can't get the option to run in seamless mode (it's greyed out). VirtualBox is running on Mac OSX.
Solved my problem. Make sure
dkms is installed in the guest OS (following command for Debian Linux):
sudo apt-get install build-essential linux-headers-`uname -r` dkms
Then re-install Guest Additions.