|Did you verify the overheating by checking the temps via the bios or monitoring software?|
Since you had to remove the heatsink to apply the paste maybe you didn't get the heatsink back on exactly right.
Or, when applying the paste you just use a thin film. Using so much that it squishes out when you tighten down the heatsink can cause problems.
Did you blow the dust out of the heatsink and fan with compressed air also?