The stock fan is pretty puny unless you get a Phenom II X4/X6 or a FX 8 series. Then again those fans are loud.
The thermal paste is a flat square and should do a good enough job. I would check the seating. I have built plenty of FX systems and none get that high with the stock cooler.
ok i checkeg the seating and the thermal past all are good, i also went as far as to reset my bios to default and also my asus control centre to default. all of these readings are at idle.