AMD Overdrive shows lowering of speed in all cores after reaching 75+ degrees celsius, that is rather high. on idle it was in the 50 degrees celsius area.
Well it does sound like you have a heat problem. At stock speeds your idle should be about 28-30c, I idle around 35c with my overclock and when playing BF3 underload at about 43-45c.
Check if your heatsink is seated properly, reapply thermal paste and reseat the heatsink to see if that helps. See if the fans on your CPU is running properly.