Just to be sure: the fan we're talking about is a case ventilation fan, right? NOT the one inside the PSU? The one inside the PSU MIGHT do what you describe since it is usually controlled entirely by the PSU itself, and never by the mobo headers.
There's a bit of info missing here. In BIOS Setup (see your mobo manual p. 25), look at the Fan Control Mode. IF you have a 3-pin fan, it should be set to Voltage. But IF you fan is 4-pin, set that to PWM. It may be that your mobo is ssending a signal for such a low speed that the fan stalls and fails to re-start. ALSO chgeck the item Fan Control Use Temperature Input. For the SYS_FAN header that runs your case ventilation fan, this should be set to the sensor on the motherboard, and NOT the one inside the CPU chip.
For background, at start-up a mobo always tells the fan to start at full speed to be sure it does start. Then in a few seconds it finds out that things are still cool and slows the fan to what ought to be required. BUT if that new setting is too low, the fan can stall. A PWM fan is less likely to do that IF it is being controlled by a header using the PWM Mode of control. A 3-pin fan, however, can ony be controlled using the older Voltage Mode.
Now, if that does not help, we go on to racksmith101's idea. In the Temperature Interval item you can set what fan speeds the header will call for at what temperatures. Within that, try setting the minimum speed for the lowest temperature higher, so the fan will never go so slow that it stalls. (You MIGHT have to select the "Manual" option of the Fan Speed Cpontrol item to get to use this feature - the manual is not clear on this point.) After you make any changes, remember to SAVE and EXIT.
One last thought. Is this a recent problem with a fan that is getting a bit old? You MAY have a fan with stiff bearings from wear, in which case your real solution is to replace the fan.