i would redo the thermal paste on the cpu cooler and check if it is fit correctly those temp look weird it could be bad sensor somewhere use this to compare the temp http://www.hwinfo.com/
My CPU is fine on temps, i have an i7 3930k Min. temp is 38*C and max is 54*C I have the Noctua NH-D14 which seems to work pretty well. my motherboard is just by far the hottest part in my case, and I could under stand one sensor being bad but all 5 sensors seem way higher than they should be to me.
Those temps are wrong. Period. It would crash long before it got there. 3rd party tools don't always,read the sensors right. I doubt they are all faulty though. Your Asus board should have come with software, last I checked it was PC probe 2, that accurately checks the motherboard sensors. Use that and use the Intel tool to check your core temps.
If it's saying overclock failed you should restore bios defaults, run memtest 86+, check temps as above, and run prime 95 to check load temps and stability
The ASUS Monitoring program gives the same readings, It passes MEMTEST all day long... one of the first things I replaced was the memory when I was having problems, I have had 3 Kits in it all with the same result. I have had 2 power supplies in it because my first one died in 3 days (Seasonic 1000w Platinum) and I ordered the Antech 1000W Platinum to keep me running. I had 2 SSD's in a Raid 0 and took one out because I thought that might be the cause. I have tried default BIOS, XMP settings, manual settings, every bios available from ASUS, I had 2 video cards the same brand and model in cross fire but one went bad and its in the process of being RMA'd, I got my other PSU back from RMA as well, I have also tried an HD 7870 Ghz edition from XFX and got the same overclock failure messsage. If im listening to music and browsing the internet sometimes my music/audi gets corrupted before it locks up and I use that as a warning to restart the computer.