I've been struggling to make it work for a few months after an upgrade from VirtualBox 4.1 to 4.2. No matter what I do, switch on and off full screen mode, remove and reinstall guest addition... Auto-resize Guest Display simpy doesn't work. Today I stumbled on this web site: http://ubuntuforums.org/showthread.php?t=1903264 and found my answer.
All I need to do is:
VBoxManage setextradata global GUI/MaxGuestResolution any
Reboot my guest OS and voila :)