I had the exact same issue. I went into the classic mode BIOS and under the Fan settingsreset defaults and rebooted and fan speeds are working normally. You can get to Classic mode from the home page of the Visual BIOS and use the option in the top left hand corner.
Thank you Phil, the classic mode worked for me, too!
(Side note: I had to go back to BIOS defaults via F9. Restoring the fan settings alone was not enough in my case.)
I know you guys solved your problems, but I'm replying in case anyone else is having the same problem and your steps didn't work.
I had the same fan problem with this motherboard, but simply selecting the default fan controls didn't solve it for me.
When I first got the mobo, I flashed it to the latest bios (0070), and everything seemed fine except my CPU fan was always running at 100% and Intel Desktop Utilities (IDU) had a constant blue spinning wheel. Repeated reinstalls of IDU didn't fix anything. I never downgraded the BIOS, I simply performed the following steps:
1) Boot into the BIOS and immediately go into Classic mode if not already there. I think the Visual BIOS was introduced with 0070, so if you have an older BIOS you may already be in Classic mode (the DOS-like looking blue background screens).
2) Load the BIOS defaults.
3) Without rebooting, go to the fan control section and select the option to restore default fan options.
4) At this point I believe I saved my changes but did not reboot. I then proceeded to manually change every option as needed (e.g., turning on RAID support, disabling onboard video, etc.).
5) Save and exit BIOS. With any luck, everything should start working normally. I could tell it worked because my CPU fan didn't speed up and IDU finally worked.
I should note that I had previously tried the Load BIOS Defaults option without also doing the fan control defaults, but it didn't work. Only the steps above worked for me.