I found that the problem was due to VirtualBox Guest Additions not installing properly (missing dependency of kernel headers etc causing a Virtualbox kernel module to not be built).
Try installing the guest additions manually through the command line, and read the errors carefully. The HOWTO below has detailed instructions.
One tip is to check the output of sudo lsmod | grep vbox
, which shows the kernel modules for Virtualbox - this was empty initially. Here's the output after fix:
$ sudo lsmod | grep vbox
vboxsf 40674 0
vboxvideo 12405 1
drm 203590 3 vboxvideo
vboxguest 173675 6 vboxsf
Once the kernel modules were done, I just had to run /usr/sbin/VBoxClient --clipboard
(on Debian 8 jessie) and the clipboard started working. Virtualbox version was 4.3.30.
The commands I ran for this setup (yours may differ) were:
aptitude install dkms build-essential linux-headers-generic
aptitude install linux-headers-3.16.0-4-586 # See HOWTO, match running kernel
cd /media/cdrom0
sh ./VBoxLinuxAdditions.run
less /var/log/vboxadd-install.log # If you get errors
A systematic way to fix this issue (and probably others) is to go through the Guest Additions HOWTO for Linux. The name of the install script has changed since 2009, but the HOWTO is still very helpful, and gives commands for Debian/Ubuntu and RHEL/CentOS style distributions.