As previously stated it is probably a bad thermal application. Which method did you use for applying it (ie pea, line, credit card) or did it come attached to the mobo from the shop?
Once you've checked and repplied your thermal paste (less is more!) I would suggest resetting your bios to default settings and checking the CPU voltage is set correctly (mine's at 1.325 currently).
I also recently had a bad bios flash that caused my CPU to overvolt and thus put the temps through the roof but I think that was a bit of a one-off. Would make sense to flash the latest bios if you don't have it though.
What case are you using and how is your ventilation? I'd say the motherboard temperatures at boot are a little high as well.