Hmmm...
Download and run a program called rivatuner.
Use it to adjust the fan speed so that it runs higher than normal.
Just google Adjust fan speed rivatuner for a how-to guide on how exactly to do it.
If that doesn't solve your problems, your power supply may be bad or your card may unfortunately be doa.