One of my mother's co-workers had an HP computer that gave the "fan defective" error message which wouldn't go away even with replacing the fan. She took it to a shop and they updated the BIOS, and that fixed the problem.
It's probably worth a shot - check your BIOS version and then check HP's website to see if they have a more up to date version.
I had an HP with the same problem.