I just returned to Intel an e8500 with the C0 stepping under warranty and received the E0 stepping back, it was my understanding this isn't a bad thing since the new revision is more stable with higher temps? I was suprised to plug it back in to my MOBO that was the exact same setup with the C0 and the temperature was super high. I've reseated everything, checked the amount of paste I applied, I'm not really a novice at doing this as I've done it probably 20 times before and everything checked out. When I mean High temperatures I don't necessarily mean at idle but at 100% load in prime95 (stock speeds on both) the C0 I never saw above 60C after time and this E0 is hitting 68C in under an hour of load. I can't really even think to OC with stock speeds hitting those temps, any one have any input ?
I know you said you reseated the cooler, but those temps indicate that the cooler is not installed correctly. Did you install the cooler while the motherboard was outside the case so you could ensure all 4 pins fully seated?
The only other thing I can think of is that the motherboard isn't reporting the correct temp for the new stepping. What motherboard do you have? Did you update to the latest BIOS?
You may want to touch the edge of a razor blade to the heat sink and CPU to see how flat they are compared to one another as well. If both are convex or concave then the heatsink will not make proper contact.