I have been faced with the same problem, when I came upon this ticket at virtualbox.org, by user "SB1234", last post:
I tried the work around to set the modes the width to 1 pixel less than the actual width. And it worked for me in fullscreen. However after exiting from full screen the resolution remained at that value. (it did not auto adjust)
Anyway after rummaging through more links online i found out that there are certain workarounds in the compiz settings manager. i was able to find one particular option that solves this problem (Yippie!!)
first you need to install compizconfig-settings-manager using sudo apt-get install compizconfig-settings-manager.
Then in Preferences->Compizconfig-settings-manager look for Utility. And then 'check' the workaround item. Finally in the settings for the workaround item, look for 'Force fullscreen redraws (buffer swap) on repaint' and check this option. Thats it!
It worked for me. I had been looking for a fix for several weeks.:D
Win7x64 bit host. Virtualbox 4.1.8 with Ubuntu 11.04. (amd64) guest. I have a intel hd 3000 on board graphics card.
This also worked for me, Ubuntu 12.04.1 LTS, Intel hd 3000, VirtualBox 4.2.2.