Does it have a 2 speed fan? ie, are there 3 wires going into the motor earth, speed 1 and 2
If so it might be the first speed is dud, and only kicking in on full speed when really hot. There is a sensor down the side of the radiator, check the wires are clean/connected tightly.
You could try powering up the fan with some wire, check both speeds to check the fan works ok.