Right. Remove the old paste. You can also use a clean lint free rag (old T-shirt is good) and isopropyl alcohol. Shouldn't use rubbing alcohol. It usually contains lanolin and will leave a film.
Suggestions for applying thermal compound:http://benchmarkreviews.com/index.php?option=com_content&task=view&id=170&Itemid=1&limit=1&limitstart=0
Then, if you still have the variation across all the cores, it's because of the difference in the thermal sensors in the CPU.
A 7 C difference, while a little high, is not too unusual.