I had similar issues with a pair of HP DX5150 PCs that I received recently. I had two different problems:
On one of the the CPU fan wasn't screwed on all the way, which caused the CPU to not be cooled efficiently. So the BIOS saw the temp rising and spun up the fan to compensate. Just turning the screws on the heatsink mounts a tad tighter actually fixed the problem.
On the other one the CPU was practically swimming in heatsink compound, which tends to cause it to act more like an insulator than a thermal conductor. After cleaning off the factory applied goop I put on some Arctic Silver and everything worked fine.
I think that was probably a fairly common issue on the DX5150 models because they were putting the Athlon 64 CPUs into a case that was originally designed around a Pentium 3 or early Pentium 4 CPU. Also, when I have had replacement CPUs or fans arrive from HP the instructions enclosed usually say to use the entire syringe full of heatsink compound instead of just a thin layer (why, I'll never know, but it tends to support my belief that they smother the CPUs with too much compound). The new models (DC5750) don't seem to have this problem, as the cases have MUCH improved air flow.