From my experience, the TIM that comes pasted onto the bottom of heatsinks is a one shot deal. You will have to scrape off the residual TIM and clean the heatsink with acetone and rubbing alcohol (in that order). Also make sure to clean the cpu in the same way.
Then get some ASII or some other thermal grease solution and apply per the manufacturers directions. Good luck (not that you'll need, this is an easy job).