How hot is too hot? (Or, how my graphics card burned my fingers)

you will need to RE APPLY your thermal paste to the GPU... it will fix your issue and your grafics card will last longer. If you wanted you might want to think about underclocking the gpu or maybe changing its voltage core.

Unless your new CPU is a significantly higher TDP model and your case is poorly ventilated I think the timing issue with the upgrade is coincidental. I suggest removing the card from your case, immobilizing the fan (some fans can be damaged if overspun) either with your finger or by sticking something inside and blasting it with canned air to clean any dust out.

The ATI 4800 series of GPUs are notoriously hot, and the reason is that the auto fan control defaults to keeping the system quiet rather than keeping the GPU cool, so they tend to idle around 75ish. If you install the latest drivers from ATI.com with the catalyst control center you can manage the fan speed manually. I have my 4870 set to a standard 40% fan speed with no issues at all and it never gets above 65C, even under extended load.