One way you might be able to get around this is to edit your xorg.conf file and force the other resolutions to be available.
The file normally lives at /etc/X11/xorg.conf.
First check to see if you have one. Then:
if you do, and you're using Maverick or later, but think you've never touched that file, make a backup of it (in case things go wrong) and then delete the file and restart (you may need to use sudo). Xorg in the latest versions of ubuntu can survive without one and will make up its own settings as best it can. If that doesn't work then put the backup back where you found it and edit it as below.
Once you have a file there are numerous tutorials on the web about how to edit it, but a good one is here: http://ubuntuforums.org/showthread.php?p=129379
If you add some lines about certain resolutions as per the link above, it should force X to use certain resolutions.
If that doesn't work however then the problem may not be with Xorg at all, but I'd try this first.