Just got a new Samsung 22" 1080p monitor and plugged it into an Acer Aspire One. I have 3 OSes in this machine, so decided to configure all 3 for the new monitor. Windows XP did a decent job at setting it up (there's an "Advanced" tab in the video preferences that has lots of cool options -- video card specific). MacOS X 10.5.5 was even better, it came up with a bogus config but as soon as I pulled the new monitors plug, it reverted to the main netbook screen and recognized the new monitor after plugging it back in. All very easy.
Unfortunately Ubuntu 9.04 was not as friendly. Although Xorg did recognize all valid modelines at boot, for whatever reason the intel driver refused to show any of the higher ones. The same thing happened when I configured other monitors in the past, but I forgot what I had done to fix it, and didn't want to hard code the xorg.conf file because I will be using different external monitors on a regular basis.
Anyway the solution is quite simple. Just force xrandr to recognize the modeline you want (xrandr --newmode and copy/paste the modeline from Xorg.0.log, then xrandr --addmode). Now go to the display preferences and your shinny new display mode will be available. Logout and login and all is done. Yay!