naveto, did you ever figure out what was wrong? I am currently having a similar problem. On start up(of my new build) i get an error that my CPU is overheating. I'm running a 2600K w/stock HSF(arctic silver3 thermal paste) on a P8P67 asus mobo. I've checked the HSF connection and everything is attached correctly. Can anyone shed a little light on my situation?
It's working fine now and I think it was because the heatsink wasn't close enough to the cpu. I had the heatsink locked in and everything, but I had to apply A LOT of pressure before it started to work properly. I don't think thermal paste made a whole lot of difference.
Also, make sure you're reading the temp not in bios. For some reason, it makes a big difference if you boot up windows and use realtemp or some other monitoring program.