I know this is probably a long shot, but have you tried entering into safe mode and seeing whether the pronlem still persists. I had a similar problem with my TNT2 when running Grand Theft Auto 3 for the first time. Part of my screen was fine but the middle part where the menu was was all looking like a "fast forwarded vcr" picture. I then discovered that for some quirky reason it had decided to set my resolution to 760x530 or some odd resolution like that. Once I changed it to 640x480 or 800x600, a more popular resolution I had no problems. My point being it could be that your new Video card has for soem odd reason decided to set your display to an odd resolution although I only experienced the static problem in Direct 3D applications - I have never set my desktop to those odd resolutions and therefore wouldnt know whether a 2D desktop behaves the same way when set to these resolutions.
If your lucky enough to go into safe mode (it should reset your display to 640x480 and so the problem should go away) go into Device Manager and look for Exclamation Points on any hardware in your system. Check that any hardware in the PCI slots is not too close to the AGP slot as they maybe sharing IRQs but the R9800XT being a beefier card is likely to want more IRQs and wont stand sharing. Leave at least PCI slots 1 and 2 free for ventilation and so that IRQs dont conflict. If you can't get into Safe Mode without this problem on either of your cards it coudl be a more serious problem. Before you give up hope there is one last thing
The fact your overclocked your previous card doesn't inspire confidence, I'm not sure about how the concept of overclocking a graphics card works but and the more experienced overclockers here can correct me as they wish here and onwards but that could possibly have contirbuted to your problem. I think ATi cards can be overclocked using utility software in Windows and I thought nVidia cards can be done using the same alternative. I'm probably dancing around the obvious but did you reset the settings back to default and uninstall the overclocking utility (if there was one) before uninstalling your old card. Also did you thoroughly remove all the old cards drivers before introducing the ATi into your system. Rival drivers with a rival card is not a good mix and is a sure sign for trouble, which is why I am double checking my work when I remove my TNT2 to put in a R9600! Those last questions may sound like the obvious but they are also imperitive for your ATi card to work.
If the above doesn't solve it and BOTH your graphics cards wont work you must have a serious problem with the AGP socket. Check your settings in the BIOS and if there is no such luck, replace your card and motherboard!
Hope this helps and good luck!
PC Spec: AMD Athlon XP 2000+, ECS K7S5A Motherboard, 768MB SDRAM PC133, Sparkle nVidia Riva TNT2 M64 32MB AGP Graphics Card, Creative Sound Blaster Audigy 2 6.1, Windows XP