While the computer is hot, feel the CPU cooler's heatsink, along the heat transfer pipe, and the cooling fins. See if you can find a spot where there's a big temp difference from one portion to the next. For example, the sink itself is hot, but the pipe is cool, or a spot along the heat transfer pipe where the temp drops off.
It's possible that your CPU cooling system has gone bad. This can happen if it develops enough internal microfractures that it basically stops conducting the heat away from CPU's integrated heat sink (IHS).
It's also possible that when you applied the paste, you used too much or too little. Either can result in less than optimal heat transfer from the IHS to the cooler's heat sink. If you pull the cooler, the IHS should be completely, or almost completely covered with paste, but not so much that it oozed over the edges of the IHS. If it oozed, reapply using less paste - if the IHS only got partially covered, then use a little bit more.