Does this fan have an integral thermal control circuit? I mean one that is specifically, independent of motherboard control? If so, do not use, allow even the default bios settings if applicable, to thermally control the fan. Sometimes it can work ok, but a fan with it's own thermal control can be more difficult to control.
Check your bios for fan speed control, it could be that based on the settings there, your fan is doing exactly what it was supposed to do, turn off when the CPU is cooler than X degrees. The important thing is that the fan turns on again every time the temp rises enough, and that the fan ramps up in speed fairly quickly from the 0-600 RPM range, as many fans aren't stable that slow, you want it to at least try to spin at > 600RPM right away, if not higher based on temp.
Of course the other possibility is as previously mentioned, if the fan is plugged into the wrong place, but more often that wrong place always powers the fan when system is turned on, it'd only be in a power management mode that such a header might have a different turn-off function relative to the CPU fan header.