What could be happening is this:
When most computers first turn on, one of their first things they like to do is rev all of the fan headers up to full voltage (makes all of the fans spin at max for a few seconds) then after this, it ramps the fans down to normal speeds and thermally controls them.
What is possible is that the LEDs on your fan only work when the fan reaches a certain speed. This could be due to the fact that to control the fan speed, voltage to the fan is either raised or lowered.
To test this theory, you need to get your CPU hot enough where your CPU fan needs to run fast (preferably at 100%). A good way to do this is to download the free program called Prime95 and use it to stress-test your CPU (select the potion...