thats odd.. are you overclocking it? do a manual chec:
run your comp for a few hours at a full load, then turn it off and touch the Heatsink/fan, if it is to hot to touch then you no there is a porblem with the cpu or the HFS.
When I changed the thermal paste, the average temp when down to about 50 degrees, but after a week, it started overheating again.
Also I'm not overclocking it.
I read somewhere that changing the power supply could help, but not too sure...