Welcome to PureOC! Let's see if we can help you. Forgive us if we overstate the obvious, we're just trying to be thorough......
-do NOT overclock yet. Always make sure your system is running good for at least a few days before OCing.
-not to insult your intelligence or experience, but you may be seating the cooler wrong even if you've redone it. Reason I say that is because the stock cooler is a PAIN IN THE ASS to get done tight and correct. I've done it COUNTLESS times and I still cuss like a sailor every single time I have to do a stock Intel cooler, believe me.
A few questions:
-what program are you using to test the temps?
-can you post a screenshot?
-what are your idle temps on all 4 cores?
-are your BIOS settings to Auto? If not, put everything to Auto. We need to isolate the problem. No manual settings or overclocking
My guess? Your CPU heatsink isn't heated correctly. Nothing else would cause this except a fubar'd CPU. Unless the temp readings are incorrect. Honestly, those are the only explanations I can see.
Give us that info and we'll help you out. Might take a bit of time to go through things one at a time though. But a bit of patience will be rewarded. You don't want to blow out a new CPU.