You sure the thermal paste was a nice even layer? Something is not right there... Worst case you can pick up an aftermarket CPU cooler and replace the whole thing. You would be able to get a good overclock on that 2500k also.http://www.newegg.com/Product/Product.aspx?Item=N82E16835103099
If replacing the CPU cooler (or tripple checking the thermal paste) doesn't help, then I would look toward the MB sensor as the problem.