Try adding the following to your screen section of xorg.conf in /etc/X11/xorg.conf . Then log out. When you log back in you should be able to pick your proper screen resolution, if Ubuntu didn't already pick the right one for you.

Seems the default display detextion tool which was introduced in 8.10 isn't all it's cracked up to be yet.

  	SubSection "Display"
  		Depth	24
  		Virtual	2560	1050
  		Modes		"800x600@60"	"1024x768@60"	"1280x1024@60"

or if you want to completelyreset your display settings:

sudo dpkg-reconfigure -phigh xserver-xorg