I had Ubuntu 10.4 working fine with the previous version of VirtualBox on a Windows 7 host.
Then I upgraded to VirtualBox to 3.2.10, reinstalled the Linux Guest Additions, and now I am limited to 1008 x 584 resolution in full-screen mode! I have reinstalled Guest Additions and rebooted the guest OS several times.
Virtualbox 3.2.12 has been out for a while, maybe that will fix your issue
http://ubuntuforums.org/showthread.php?t=1153437 This worked for me.
EDIT:
I spoke too soon. After a "sleep" it changed to a low resolution again. And now that I think about it, I really would prefer that Guest Additions would detect things properly instead of me having to edit the xorg.conf myself, mainly because it can probably make it more ideal than what I copy and paste from a web forum. Any chance of fixing Guest Additions? Or should I try upgrading to Ubuntu 10.10?