Hmm. I'm curious what case you are using?
Make sure all power to everything is OFF.
You will want to take the mobo out of the case before removing the cooler. You should then be able to simply release whatever clips are holding the cooler onto the CPU. It should come right off. There is a proper technique for each mounting arrangement, and you shouldn't have to use brute force. The paste will come off easily by wiping with a cloth or paper towel. Maybe a little alcohol. If it has a thermal pad, it will come off with a little scraping with a plastic putty knife and wipe with a little alcohol.
While doing this, check to see if maybe the thermal compound was applied wrong, or maybe the cooler was not installed properly in the first place, causing it to overheat. It happened to me once.
Also consider the possibility that the voltage was set too high on the CPU, or maybe your guy sold you an overclocked chip?
G'luck