I couldn't get my resolution in Ubuntu beyond 1024*768 the other day, and spent a whole day fiddling around with it.
I was quiet surprised (and embarrassed) when my colleague pointed out you have to specifically set the monitor you are using before other resolutions are available.