Two different possible cures...
I've found that with my 5800 Ultra and my 5600 Ultra that if you are using Windows XP that this is caused from the Restore feature. If you disable SYSTEM RESTORE on your drives that this problem goes away, also stop indexing on drives. It also can be caused by a smaller power supply.
I recently had a systems video stop functioning correctly and displayed only a large bar code of colors even during the POST with my 5800 Ultra, I RMA this card back and bought the 5600 Ultra and had same problem. I then RMA my motherboard and bought a 2.0 and sent my 1.0 board back thinking it was the AGP slot because PCI cards worked.
The 5800 Ultra worked fine since March of this year before this happened, I had a 350 Watt Power Supply.
Once I realized it wasn't either the video nor the motherboard, I replaced the Power Supply with a 600 Watt and everything has been fine since.
These are just other considerations to check.
I also have a system with a 4600 TI and found that with this card that depending on the motherboard that you must disable the fast write or where it asks SUPPORTED which if I remember correctly is for FAST WRITE within bios to fix any problems with those cards, lock ups and stutters go away.
(2) Asus A7N8X Deluxe 1.0 and 2.0 Boards
Geforce FX 5800 Ultra and 5600 Ultra
AMD Athlon XP 2700+
1.5 Gig Corsair XMS RAM Dual Channel
(2) Plextor CDRW Drives
(2) 80 Gig Seagate SATA Hard Drives