I have the same problem with my system. My specs are as follows:
Athlon 64 3400+ (running at 2.2ghz, stock speed)
3 x 512MB Kingston DDR PC3200 (running at 400mhz, stock speed)
Sapphire Atlantis 9800pro 128mb (running at stock speeds for GPU and DDR)
Samsung 915N 19" LCD monitor (1280x1024 60hz native, VGA cable)
Windows XP SP2 slipstreamed
Omega drivers 2.6.71 (based on Catalyst 5.9 but I had the same problem with many versions of Catalyst and Omega with this monitor)
I recently replaced my CRT with this LCD and was unable to get fullscreen until I tried 640x480, normal2x, fullfixed true as recommended in this thread. I get black bars which sucks but is tolerable.
FYI, I can run Dosbox on my laptop, which has an LCD screen, at many different resolutions without changing any major display settings.
Is LCD the problem? Could the problem be that my LCD's native resolution is 1280x1024 which is 5:4 ratio? Does it matter that my monitor has a VGA cable, not DVI?
I can play Windows games at 1024x768 just fine (with the expected pixel stretching).
If I can help test, please let me know!