By the sounds of things,
You didnt clean off and replace the old paste when you removed the Hs, You should do that everytime you remove the cooler, I think once you get your new paste on there you should see your temps go back to 'normal' if not improve
Good job on cleaning it out though
Thanks a lot for the info. I will actually do that when the new paste arrives by Monday. Also, I have another question to you and everybody out here:
Will a solution of 70% ethyl alcohol be OK to remove the old thermal paste? I am not able to find a 90-99% isopropyl alcohol near my home's drug stores.