1. Be carefull when removing the cooler. You can damage CPU, especially this series of Bartons. You must have a lot of place aroud (if you have a good motherboard. You can see here the clams you must free to remove it.
http://www.directron.com/howtocmdp55g11.html http://www.mysuperpc.com/cpu_cooler.shtml
2. You must see alot of dust inside the heatsink, underneath the fan. Take it away and that should do the trick.
3. Clean the thermal paste from the heatsink and the CPU surface. Use smooth paper or some clothing. Not hard surfaces, you may damage all.
4. If you are not sure you can manage this, buy a new cooler, it's somethinh around 7-10 $.