I had the exactly same problem two weeks ago when changing the heatsink of an AM2 CPU. It was "glued" quite well, and I spent an hour trying to detach it.
Not sure about AM3, but I think it has a lock mechanism too. An AM2 has one, but not too good to maintain the CPU when removing a well-glued heatsink.
Removal of a locked CPU is easy: you probably cannot break anything, except probably the link between the CPU base and the motherboard. Putting a CPU on a locked base, on the other hand, is not as safe and easy to do. You may end up with damaged pins on the edges if you force it too much (and if it is similar to AM2, you cannot unlock the base and put the CPU with heatsink on it, so the only way is to force it).
So I strongly recommend detaching the CPU first from the heatsink. The problem is that:
- You may not force too much if you do not want to damage the CPU (even it's quite difficult).
- You must not force the pins when detaching the CPU. Damaging the pins is much easier.
- You may not use water, heat or other things trying to detach your CPU, since those can damage the CPU itself.
- Using a knife will be an extremely bad idea. By the way, if you damage the surface, the heat will not evacuate well.
To detach the CPU from the heatsink, try to push it to the side, parallel to the surface of the CPU, rotating from time to time. That's what I've done.
What to add? Ah, yes: good luck!
Note: this happens because you (and I) put too much thermal paste. Try putting just a few drops the next time, it's quite enough.