Com o Ubuntu 12.04 como host e convidado, segui a resposta do wfudge.
Isso requer que outros pacotes sejam instalados:
sudo apt-get xserver-xorg-core
Depois disso, executamos esta linha modificada do wfudge sugerida pelo apt-get:
sudo apt-get install virtualbox-ose-guest-utils virtualbox-ose-guest-x11 virtualbox-ose-guest-dkms virtualbox-guest-x11
Depois que o convidado do Ubuntu não inicializou na GUI, então com Ctrl + Alt + F1, logou em um console e executou:
sudo apt-get install ubuntu-desktop
Reinicie e pronto. Agora posso obter resoluções mais altas até 1600x1200. Ainda não 1920x1080 (host), por isso não é em tela cheia, mas pelo menos é muito melhor do que eu tinha antes.
Eu acho que é um problema do VirtualBox, mas quando usado um host do Windows não tem esse problema ...