It is usually a good idea to replace the thermal paste, yes. But if you can't, you should still be okay. Just make sure you don't wipe any of it off.
Maybe secure it again and run it for a few minutes to warm the paste up a little. Sometimes you get a tiny bit of sideways wiggle room, be patient should come off without too much force.
You can goto your local Radio Shack store and get some Artic Silver 5 Thermal paste to replace your existing paste.
Like womble said, secure it. Heat it up. Run an antivirus scan. Turn it off. Unhook it, twist. Don't pull straight up. The processor will come out of the socket.
If you don't have to do this, don't do it. There is always a chance of bending CPU pins.
When removing "stuck" heatsinks, adding a little bit of torque usually makes it easier to pull it off.
Pulling straight creates a vacuum under the heatsink that draws the thickened/settled paste back in, which requires a fair amount of force. Twisting breaks the surface tension to let air in which makes it much easier to separate surfaces.