The stock intel coolers are kind of a pain in the ass. I've had several cases where I've thought the heatsink was in all the way, when in fact some of the pins aren't all the way snapped in. Double check that. Also, you made sure to clean off both the processor and the cooler with rubbing alcohol before you put new paste on didn't you? Did you spread a nice, thin even layer?
Read again brother, he took off the heat spreader, not the heat sink - the cap that protects the silicon die of the CPU.
As for you you filthy little tinkerer, i HOPE you didn't put too much paste in there - all you have to do was put enough to cover the die & connect to the spreader. Did you get the spreader back on nice & tight?