Wow
are you 100% certain that resolution is supported, and have you tried with some other resolution of the same relation (like 1280x800 for example)?
Then my next questions would be..are you using an appropriate display driver (nv for nvidia cards, ati for ati cards or fglrx for those that it supports, sis for sis chipsets, ...) instead of something more generic?
That does look quite ugly. I'm having no problems with a resolution like that (ratio 1,6) with Feisty, and have never had with Ubuntu. So..I would guess it's hardware-specific or driver-specific.