When you reinstall a cooler, you should clean off the old paste and reapply new.
What is your case, and where is the radiator mounted?
What is your temperature at idle?
If it is more than 10-15c. over ambient, your cooler is not mounted well, or it is not getting sufficient fresh air to do it's job.
Have you overclocked?