Well in Linux you GUI enviroment is called 'X Windows'.
The behavior of it is controlled by a configuration file, which depending on your version of Ubuntu, is located in /etc/X11/ and is xorg.conf or XF86Config-4. Now you should be using a recent version of it so that xorg.conf is probably the correct configuration file. (if you have both files then it will use xorg.conf first, then if that's not present it will try XF86Config-4, and if that's not present it will try XF86Config.. in that order)
In that file you can place the horizontal and vertical refresh rates of your monitor. X will also try self-detect the values of your monitor every time it's run and sometimes that works well, and sometimes not (usually a hardware issue)
If those values are present then it's possible that those values are not accurate, so that X windows does not think that your monitor is capable of higher resolutions.
To fix that problem you have to go in and edit the file and put down the actual range of refresh rates you monitor can handle.
Here is a sample from my xorg.conf file...
Section "Monitor"
Identifier "SyncMaster"
HorizSync 30-96
VertRefresh 50-160
Option "DPMS"
EndSection
So change the maximum values of HorizSync and VertRefresh to whatever your monitor can handle.
That's one possibility.
The other possiblity with that file is that your able to tell it what resolutions you want to be able to run at and also color depth... (8bit, 16bit, 24bit (called 32bit in windows.. same different))
So it could be that the highest aviable resolution the file says you want to run is 1024x768.
To fix that you have to tell it what resolutions you want it to be able to run at.
Here is a sample from my xorg.conf file:
(please note that the Anandtech forums software removes lots of whitespace)
Section "Screen"
Identifier "Default Screen"
Device "Nvidia AGP"
Monitor "SyncMaster"
DefaultDepth 24
SubSection "Display"
Depth 16
Modes "1280x1024" "1024x768" "800x600" "640x480"
EndSubSection
SubSection "Display"
Depth 24
Modes "1280x1024" "1024x768" "800x600" "640x480"
EndSubSection
EndSection
The device names realy shouldn't be messed with. Just use whatever it's using. The important lines is "DefaultDepth" for your default color depth, and the "Modes"
So if I wanted to run at 1600x1200 I'd have to change
Modes "1280x1024" "1024x768" "800x600" "640x480"
to
Modes "1600x1200" "1280x1024" "1024x768" "800x600" "640x480"
and then I'd be able to run at 1600x1200 if my monitor and hardware supported it.
The other major thing that causes problems is hardware limitations. Obviously you've run high resolutions before, so that's not the issue...
However with some video cards... Namely the Intel embedded/on-board style video cards that you commonly find in Laptops and inexpensive computers have to interact in a unusual way with the BIOS. I don't know all the details, but what happens in the bios is programmed with with standardized VESA (a video standards orginization) resolutions.
In Windows the drivers have the ability to dynamicly change these values.. Intel never bothered to get that sort of thing to work with the linux drivers so if your using a non-standard resolution... Like if your using a 'wide screen' display.. the vBIOS won't allow you to use a non-vesa-standard resolution.
So in order to work around that you have to resort to using a ugly hack to trick the vbios into giving you the resolution you want. Now I don't know your hardware, so I won't go into that and possibly confuse you.