I had this problem when I first installed my board. I fixed it by changing a setting in the PC Health section of the BIOS. I can't recall the name of the option, but I know it was the last option in the PC Health section.
By default the option is set to "Auto". Other options are "PWM" and "Voltage". Apparently it couldn't figure out what my CPU fan was on Auto, so I set it to PWM since I have a PWM (4-pin) CPU fan. All is working now. If you have a 3-pin CPU fan, set the option to voltage.