Same as above, remove the heatsink and fan unit and clean any excess thermal paste off. You can use rubbing alcohol or something similar for this. Don't use anything oil-based though. Apply a very thin layer of thermal paste to the base of the heatsink as too much will also cause high temps. When you fit the heatsink make sure you have a good solid contact with the CPU and that ALL of the clips lock into place. It's best to work on opposite corners - to one corner and then the opposite corner as opposed to going around them in turn. You can google for more info on how to apply thermal paste if you want to.
Also make sure that your case has good airflow through it. Ensure there is no dust as dust is a very good thermal insulator. A can...