I was troubled with the screen resolution on Virtual Box on Windows 7 x64 as host and Ubuntu 12.04 LTS desktop as guest. I had raised the video memory to 128 MB, installed the VirtualBox Linux Additions, but it was still a no go. When checking the display setting in Ubuntu I could only choose between 800x640 (4:3) and 1024x768 (4:3).
Ticking the checkbox Enable 3D Acceleration in the virtual machine settings made it work. After that, when the guest window was resized, the size was reflected in the Ubuntu display settings. By turning on full screen mode I could use the full 1600x900 resolution in Ubuntu.
Hopes this might save someone's hair.
UPDATE: After enabling 3D acceleration Ubuntu became extremly sluggish. So I unticked the 3D acceleration and I could still enjoy full screen resolution.
apt-get install virtualbox-guest-dkmsafter each kernel update. – Thorbjørn Ravn Andersen Dec 10 '12 at 14:34