Tried Overclocking

I've got:

i5 2500K (was stock 3.3GHz), overclocked to 4.5GHz.
Asus P8Z68-VPRO.
Corsair A70, cooler.
8GB DDR3 Ram, 1600MHz.

I used these instructions:
Intel i5 2500k Overclocking Guide 4.5ghz settings. Asus P8P67. Air cooling. Stable. GLHF Computers - YouTube

For comparison, I ran the stress test before and after.
Both stress tests were 30 minutes long.
My idle has increased the temperature from 28c to 33c.
My Prime95 stress test has decreased the temperature from 80c to 72c.
It passes all of the IntelBurn Test V2 tests, before and after.

The only setting that I changed (that might account for cooler temps) was the Fan Controls.
They no longer scale with temperature, and are always on at 100%.
So, with the fans at 100%, the CPU is actually cooler during a stress test than before.

But the part I don't get...
Why would it be cooler under stress, but hotter while idle?

The simplest explanation is that your motherboard's fan speed curve is not calibrated for your cooler setup, so it runs at less than 100% when it sees "high" temps or it throttles back the speed too early once it gets below 80, which keeps it at 80 instead of just max cooling. Many manufacturers don't set up the fan curves for max cooling but instead try to use a curve that gives good cooling within certain ranges without making it sound like your PC is about to take off from the deck of an aircraft carrier.

My intel reference board has settings for points along the curve specifically to allow for setups like this -- I'd be surprised if yours didn't have something similar.

Makes sense.

i agree with ^. make sure in your bios that "smart fan" or whatever your mobo manufacturer calls it is turned OFF and you have it set to 100% i myself have my cpu watercooled and the fans are on a rheostat. mostly because if i run them wide open it sounds like a 747 and i can hear it through my Razer HP-1 canz. i would make sure that your fan is spinning at idle to make sure you do inadvertently cause a meltdown.