It's been awhile since I checked my computer's "Health" and I can't remember how my temps were before. For this OC, how does this look???
Temps are high for sure. You tried cleaning out the fans attacehed to your cooler to make sure of good air flow and obviously re-seating the cooler its self with a good quality thermal paste to ensure good transfer.
High temps are high. Time to clean the dust out of your cooler (and possibly reseat it) and check the fan RPM.
For near 4 ghz on 1366 they are okish, you could probably do with a reseat of your cooler (and a clean mabye) I don't think you will knock huge amounts off of those temps though.
Mine only hits to 66c when running Prime64 at the same frequency (3800). You have hyperthreading to contend with but still.
just going on what I remember of CPU-Z (not run it in a while) doesn't it show you what your current clockspeed is, ie so when changing states it reduces the multiplier. if it does it would suggest that its running full speed > meaning its still sucking up those volts and making heat. have you changed power options to disable energy saving features?
You can use Argus Monitor to see what your CPU is doing in real time, amongst other things. Temperatures are also very accurate.