So did you try a different Catalyst version, maybe one that came on your support cd, is the behavior all the same ? The one you get on the support CD may be better optimized for your video card.
Did you try settings in ATI Catalyst Control Panel, like Monitor Panel Properties, Display options,
Refresh Rate:
TweakGuides.com - ATI Catalyst Tweak Guide
If adjusting the refresh rate doesn't help, then maybe you can try a different monitor connection?
(We take it that your card is not overclocked)