I'm using Catalyst 8.78 (installed by synaptic) + Ubuntu 10.10.
I've also made the same tests on this configurations:
Catalyst 10.12 (from ATI.com) + Ubuntu 10.10
Catalyst 10.12 (from ATI.com) + Ubuntu 9.10
Video card: ATI HD4770
Display: Samsung SyncMaster 795MB (CRT)
Xrandr version: 1.3.3

The problem:
My CRT has 1600x1200 max resolution. Open-source drivers automatically set up xrandr to use this resolution (and works perfect), but fglrx can't surpass 1280x1024.

The tested solution:
I've tested adding a 1600x1200 mode using both CVT and GTF commands. Results: both could make the display work at 1600x1200 but there is a huge amount of black borders (about 15% of the screen).

So, I got an underscan problem. I've tried scaling the screen using catalyst control center, but since the amount of borders is too high, CCC could reduce them just a little. Well, maybe the borders are there because the VGA is sending wrong horizontal sync and vertical refresh rates to the monitor.

Xorg.conf - adjusting Horizsync and Vrefresh:
3 tests were made:

1) Got this values from an old xorg.conf when I had a nvidia card (but same monitor):
   Horizsync 28 - 33
   Vrefresh  43 - 72
2) Got this values from monitor manual (I did supose that vertical refresh and vertical sync are the same because I couldn't find the first one on the manual):
   Horizsync 30 - 85
   Vrefresh  50 - 160
Manual link: http://www.samsung.com/us/support/su...mdl_name=795MB

3) Just used the default "aticonfig --initial" generated xorg.conf file (monitor info should be automatically get by fglrx).

Results: all were the same! I mean, all the xorg.conf resulted in the same ammount of border at the same position! Is like fglrx is completely ignoring xorg.conf!!

Another relevant result that makes me believe in this is that adding a line in xorg.conf like this:
Modes       "1600x1200" "1280x1024" "1024x768"
or this

ModeLine    "1600x1200_60" 175.50 1600 1664 1856 2160 1200 1201 1204 1250 +hsync +vsync
Makes absolutely NO difference. I mean, when I do start X, there will be no 1600x1200 option available on xrandr until I add them manually using the "xrandr --newmode" and then "xrandr --addmode" commands!

What's the secret? I don't mind installing another version of Catalyst if there's a trick for a specific version or even installing another version of Ubuntu.