Just keep wiggling back and forth. IT takes quite a bit of force, especially when it has been on for a while (the thermal paste is like glue). I would try Cheezeit's suggestion. Try and put the CPU at full load for a little bit, then quickly shut down and try to pull it off...
If the CPU actually comes out with the heatsink, there could be problems. Some of the pins may be bent, so make sure to check it over very well. If there are a few bent, you may want to try to slide a credit card through the pins to try and straighten them out. Be extremely careful, you definately don't want to break one off...