It's quite strange that the CPU is overheating even when you replaced the thermal paste. At this time I could only suggest making sure that the fan wire is connected properly and that fans are working at their full rev. Also, make sure that the heat sink is not loose, if the heat sink is not touching the surface of the CPU then it won't work.