What's the new psu? It could very well actually be worse than what you originally started with. Not necessarily because of quality, but age, use, abuse suffered from your bud.
Some pastes dry out. That in itself isn't an issue, the 'paste' part is just a medium to contain the silicates and other stuff that actually does the thermal transfer work. However, once dried it's 'bonded' to the cpu. If you break the bond (sorta like breaking the bond on a suction cup stuck to glass) by jarring the heatsink, excessive vibration from a junky fan, rock the pc case pretty much any force applied to the heatsink, then the silicates loose cohesiveness and don't work well anymore, temps skyrocket. Requires a good cleaning and repaste to fix.