We'd need further information on your power supply to be able to determine if this guy is giving you proper information.
Frankly though, if it was truly a power issue, I don't think it would be the fan on the GPU that would suffer. If your GPU wasn't getting enough power, it simply wouldn't work (freeze, crash, scrambled images, etc).
My first attempt to rectify your particular issue would be to determine if the cooling fan on your GPU is dirty. If its got dust and such in it, you'll need to clean that out by blowing compressed air into it. It could be as simple as that.
If that's not the issue, there could be two other fixes. One could be that your computer case simply does not have adequate airflow to allow the GPU to cool itself. This can be rectified by either adding cooling fans or cleaning the existing ones.
The second possible option could be to adjust the fan speed on your GPU so it runs faster. Sometimes the factory default settings keep the fan on the video card from reaching high speeds to make it quieter. If could need to be manually set at 80-100% if your case isn't allowing good airflow.
Back to your power supply though. Can you determine the Brand and Model # of your power supply?