Also, make sure that the video card fan is spinning up properly.
(as well as all the others)
If a cooling problem is suspected, an old trick is to open the side of the case and point a desk fan at the innards.
Start up and see if the problem disappears. If it does, you know that you have a cooling (air circulation) issue.
If none of the above works, you could try underclocking the card a bit.
I think the free utility Riva Tuner will let you do this.
Cool bits is another one.
Most all the video card utilities are here:
http://downloads.guru3d.com/download.php?id=13