the stock themal paste is like a very hard wax almost, it usually holds onto the cpu's so hard its best to warm everything up first then twist side to side and hope you get lucky. since you managed it, thats for future reference!
Yeah it took the cpu right out of the slot, lucky it didnt damage it.
Meh, that's fine once or twice, just don't make a habit of it
Although it is a bit of a scare when it first happens!