When you applied the new thermal paste how much did you use? You only need just a little, small pea size dab in the center of the CPU, otherwise the paste doesn't allow the heat to transfer to the CPU cooler properly. To much paste and it inhibits the heat from transferring to little the cooler wont make proper contact with the CPU.
Use rubbing alcohol as pure as you can get and a coffee filter to clean the surfaces. alcohol evaporates with out a residue and coffee filters do not leave lint behind.
most likely the issue is with the cooler and how it is attached.