Once all the pins are out, just give it a little twist as you pull on it. If they went and put a thermal adhesive on there, then they should pretty much owe you a new CPU because that would be pants-on-head retarded. So yeah, thermal paste can get sticky... just twist it a bit.
Also, make sure you totally clean the CPU off and apply new TIM. There's lots of guides on how to.