|Did you clean of all traces of the old heat sink compound and replace it with new?|
Did you replace according to the manufactures instructions? To much can be as bad as to little.
Are you sure the fan is plugged in correctly to the required place on the on the board. Does the fan spin?
Failure to do any of the above will cause a CPU to overheat very quickly and the BIOS to switch the computer off.
For future reference the way to remove a stuck heat-sink is to rotate it to break the seal. Pulling it of directly will never shift it and could result in damage to the CPU.