The thermal paste is probably stuck and formed a bond. It's one of those things you sort of have to just do, but do right. lol.
If you twist, you'll bend all the pins on the chip, so don't try and twist it off.
If you pull too hard the pins may stay in the mb or the chip will come out with the rentention bracket still down and could damage a pin. (i do it this way and don't have an issue, but i'm not advising it)
See if you can get something flat like a screw driver or butterknife inbetween the heatsink and chip and break that seal the thermal paste has.