High temps running Prime95

That's really high an aftermarket heatsink is in order.

It has one.

If it has an aftermarket heatsink, then it's not installed correctly or has no thermal compound or something. There's no way it should be getting that hot at stock speed.

is the cooler branded? if so post its name.
as above have said, thermal paste needs to be checked and applied, good branded stuff like arctic coolings mx-3 compound is great. (cheap 2 at 5-7 pounds)
also was thermal management (enabled) in bios, if so turn it off so your cpu fan can run at max rpm off the bat.
also while in bios check that its set at default settings by loading the optimized defaults.

Once you start running at high overclocks or high loads (let alone both), your case choice also becomes really important. The best cooler in the world will not help if you are not moving enough air through the case.