Same thing happened to my about six months ago.  About three months later, the power supply fan started to make a grinding sound and then died too.  I'd suggest you clean the CPU fan and power supply fan while you're in there replacing your graphics card.

You can buy cool little bottles of compressed air in pretty much all computer stores.  Using one of those beats the stuffing out of trying to clean a fan by blowing on it... which not only doesn't work very well but you end up eating half the dust you blew out.

Sandy