The graphics cards are not bad. Even Apple Store's have proclaimed them as not being bad. They don't fail in any version of Windows or Linux and the they work fine in Tiger and Leopard.
It wouldn't be the first time I've proved the Apple Store wrong on a machine's diagnosis.
The things working fine in Windows or Linux is suspicious, but it's not proof, and it's also the first I've heard of it.
Here are the possibilities and my logic behind them:
1- The drivers are buggy.
2- The cards have a design flaw and are buggy.
3- The cards aren't buggy but are prone to failure.
4- The logic boards have issues.
1- if this were the case, Apple should have a class-action lawsuit on its hands for willfully obsoleting machines through making them fail.
2- if this were the case, all of the cards would have the problem (or at the very least, all of the cards of a specific revision), and it would have been immediately visible on ALL of the machines as soon as the update was installed. This could be fixed with a software update and would have been an issue on all platforms, though the issue may have been accounted for in software before it ever reached consumers.
3- if this were the case, the cards would have varying degrees of reliability. Some would work, some wouldn't. The issue wouldn't necessarily arise immediately with an OS update for everyone, as the card may fail after the update. In the field, this has been my experience. Every machine that came through our doors had OS updates installed, and we never ran into issues with installing an OS update that couldn't be explained by bad RAM, bad hard drive, or bad hard drive cable. Also, if this were the case, known-good cards would exist, and replacing the graphics card would make the problem go away.
4- I've seen logic boards pass surges from lightning through and fry the graphics card. So, this is plausible, too.
----------
Unfortunately, people have had Apple Store blindly tell them that their graphics card is failing. They pay the $250 to have it replaced, only to have the problem return. A few have even had their whole logicboard replaced. Still the freezes persist. I've had this happen with different hard drives/SSDs and via Netboot. It's frozen when it had 1GB, 2GB, 4GB, and the current 6GB of ram in it. My iMac is on a known good UPS with power filtering capabilities. Thermal levels doesn't effect it at all. It'll crash when idle, waking from hibernate or sleep, or when encoding DVDs. Stressing the GPU doesn't matter either. It'll crash when reading a Word document, playing music with the screen off, or when playing games such as Halo. The only replacement graphics card that would fix this is the Nvidia GeForce 8800 GS card that came on the high end 24" iMac8,1. But that card has the somewhat faulty 8800 GPU and it is too big to fit in a 20" iMac.
Not everyone tests the parts that Apple distribution sends, and I have had to tell Apple multiple times on individual orders that they sent me a bad part. They do send bad parts.