Yes, you should. There are a lot of thermal compounds out there, and it would be unfair if I just recommend one, so I'm linking a thread about thermal compounds/pastes:
http://www.tomshardware.com/forum/360490-28-best-thermal-paste-lowest-temps
Read that and then decide.
Of course you would also need to know how to apply the thermal compound. If you put too much, the compound will spill over to other parts of your system and cause more over heating and shorting.
Here's a a video guide for you:
http://www.youtube.com/watch?v=fRRWbQUqW1Y
There are lot of techniques that you can do to apply the thermal compound, but I'd personally go with the pea method.
Anyway, just a few important reminders in reapplying the thermal compound:
1. Make sure you gound yourself before you touch your CPU
2. Clean your cooler heatsink and CPU with alcohol (the purer it is, the better) and a lint-free cloth
3. Don't overdo the application of the thermal compound
4. Check temps after you've made the switch; if it's still hot or even hotter, reapply again, otherwise you'll be fine