Umm... it would help if you told us what heatsink/fan and CPU you're dealing with. They're often different for Intel vs. AMD, stock vs. after-market. I'd suggest that if you can get it to move freely when you release the levers, you're 90% of the way there. I'm guessing you haven't completely opened up the levers or you need to twist or turn the entire unit to free it.
HOWEVER, you really need to be careful when doing ANYTHING with that sort of stuff. There needs to be some thermal compound between the CPU and heatsink, and everytime you disconnect the two, you're hurting the bond that is created between the two elements by the compound. So you should really only pull the 2 apart when you plan to put it all back together with fresh compound (Artic Silver 5 is my recommendation). I suggest alcohol rubs to remove the old compound, and make sure you get it very clean. And the new compound should never be more than a dot, since pushing the CPU and heatsink together will cause the compound to spread and pour over the sides and into the contacts of the CPU if you have too much (AKA VERY BAD).
You really need to do research on this type of work... it's not something that should be taken lightly because you'll only end up hurting the hardware or ruining it if you screw it up.