Compaq D510 SFF desktop machine.

As soon as you turn it on(with cover on), it immediately shuts down, blinking the power-on LED at you in red, 1-second intervals.

According to the manual, this indicates the CPU is overheated, but the heatsink is COLD, and the machine has not been running, so frankly, I don't believe that.

Have checked the CPU is properly seated, as suggested by the manual, and have replaced the heatsink(after making sure it was spotlessly clean, and so was the top of the CPU, and smearing some silver grease on the top of the heatsink to aid in heat transfer).

Does anyone know why am I getting this "Overheated" symptom from the system, when the system is cold?

Does the heatsink fan actually come on?

If the heatsink fan has failed it can cause this...HP/Compaq has a limited BIOS, so some of the detailed warnings in a standard BIOS may be combined into more 'generic' warnings.

Fan comes on for about half-a-second, then the machine shuts off and starts blinking the red LED at me.

The fan speed sensor working ?

should be at least 3 wire unit/plug

Looks like the only way to test it is connecting it to another system
Very Long jumpers wires may be required

OR
Find a known working fan that has the sensor wires (3 maybe 4)
Connect it to the Mother board cpu connection and fire it up
Good idea to hold the fan over the other fan and heatsink
Just in case

Just for grins and giggles
make sure the CPU connector is hooked to the CPU connector and not the case fan header

Plug on CPU fan is 3-way type, but only two wires are actually used - the sensor wire(normally yellow) is actually connected to the +12v terminal via a splice in the wires to the fan. This does not look like someone's hack, it looks professionally done, so I think this is supposed to be this way. I have several other case fans - I will plop one in there(just sit it in), and disconnect the old fan and see what happens.