You should definitely remove any old thermal paste or pads, otherwise heat transfer will be adversely affected. Methylated spirits, isopropyl alcohol or even acetone (use with caution!) applied with a lint-free cotton cloth should make short work of any leftover gunk. Make sure you apply the new paste properly.
Here's a guide.
The temps you report are perfectly fine at first glance (I'm assuming you have an LGA-775 Prescott, which are rather warm anyway), but what do they go up to under load?
To really stress your system, a test like Prime95 will do the job.