I, too, am more inclined to suspect the mobo's control of the fan, and not the fan itself. When you first turn on power, all fans controlled by mobo ports will start up at full speed. After a few seconds when the BIOS completes the first part of its POST, it will get around to actually initiating automatic control of the fans and slow them down because all the components are still cool. Later it will speed them up again as things warm up. It appears that, in this process, the automatic control of the CPU fan is shutting it off completely. And MAYBE that is related to how the BIOS recognizes and deals with the CPU and its built-in temperature sensor. So a BIOS update may well be the solution.
There are three other things I suggest you check to confirm your information.
1. All such fans operate at 12 VDC or less. That is the voltage from an automobile battery. So you could remove the CPU cooler fan from your case (or, bring a 12 V battery to your computer) and connect the fan to that supply. Disconnect the fan from the mobo port. On the fan's connector, the contacts are Pin #1 for negative, and Pin #2 for positive. If it's a 3-pin fan, the wires are Black and Red. If it's a 4-pin fan, they will be Black and Yellow. If the fan starts immediately and keeps running smoothly, you know it is OK.
2. Another more unlikely cause is a poor connection at the mobo port. Many modern mobos have a special protection system for the CPU cooler. They monitor the speed of the CPU cooling fan. That speed is a pulse signal generated inside the fan motor and sent back to the mobo on Pin #3. If the mobo (once it is actually doing its fan control process) senses that the fan is NOT turning (that is, it gets no signal from the fan on port Pin #3) it will shut down the whole system immediately. This is to prevent overheating of the CPU with no cooling. Note that the system for this fan does not even wait for the measured temperature inside the CPU to go high - it pre-supposes that that disaster will be inevitable if there is no fan cooling. So, check carefully the connection of CPU fan to mobo port.
3. All of this presumes something: that you actually do have the CPU cooling fan plugged into the mobo port marked for CPU_FAN, and NOT somewhere else. Is that true?