Hi slyphnier, Any time that you remove your CPU heatsink you want to remove to old paste with a Q-tip or a cotton ball with a little isopropyl alcohol on it. Clean it very well so there is no left over paste, then re-apply new paste like Artic Silver 5 or OCZ Artic Freeze, only put a small rice grain size of paste in the center of the CPU then re-install your Heatsink.
Take a look over this guide if you have any questions or concerns about how to do this properly: http://benchmarkreviews.com/index.php?option=com_content&task=view&id=170&Itemid=1
Also here is a short list of the best TIM's available today: http://benchmarkreviews.com/index.php?option=com_content&task=view&id=150&Itemid=62&limit=1&limitstart=12
If you want even more help on the matter there are also good youtube videos showing how to properly do this.