Are you using the stock cooler? If so, that could be part of the issue. The other issue could be case ventilation. Changing the thermal paste only helps if the ambient temps within your case aren't skyrocketing, and you have a cooler capable of keeping your cpu cool.
I run a FX 6300 on a 990FX board. My CPU idles 10-13C, tops out around 45-50C full load. I have a full tower case with 2x 200mm intake fans, 2x 200 exhaust, 1x 140 exhaust, with an Antec Khuler 620 on the CPU, top mounted push/pull exhaust.