New computer...very high CPU temperatures.

I recently installed a zalman cpns9700 cooler on top of a e8400 in a p5q deluxe. At stock settings the cpu idles at 40 and loads at 52. When i overclock it to 3.6, it idles at 44 and loads at 60. It cant complete the stress test on prime 95. I reapplied the thermal paste after cleaning it with 90% alcohol. No change. I was wondering if anyone had any ideas. I took temperatures from speedfan, core temp, and the asus pc probe 2. They are all slightly different, but all very high none the less. I really want to overclock it to 3.6, the temps im getting are actually worst then the stock fan i think. Any help is appreciated. Maybe after several weeks the temperatures will get better, i just installed it today.