Never in my life have I heard of having to take out the entire motherboard to replace a heatsink and fan...

How did you handle the motherboard? What surfaces did you place it on... etc... How did you handle the CPU? How did you scrub off the old compound?? We need details on how you went about this procedure...

Sounds to me either you messed up the CPU or the motherboard... I am not as optimistic as nihil ... I doubt replacing the fan with another one will help now... I think the damage has been done...