If the fan is working properly and is plugged into the proper place on the mobo - then it's gotta be either a BIOS problem or a motherboard problem.
So, I'd first suggest plugging in another fan. That'll check to be sure that there's no damage to the fan that's preventing the BIOS from recognizing it. Also, reset the BIOS to default/fail safe values.
Once that's done, it's either a BIOS flash (be very, very careful) or a problem with the mobo.
If the flash doesn't fix it, then you're looking at trying another motherboard (not fun!).