Is it an 80mm fan or larger? Some of those spin at low rpm's, and the motherboard can't detect them. Sometimes a BIOS update will do the job, sometimes not - depends on 1) if a BIOS update can fix the problem, 2) if the motherboard maker knows about the problem, and 3) if the motherboard maker feels like going to the trouble of supporting its products. If you've got all three, you're in good shape.
Or maybe the fan's just defective.
What motherboard or PC is this?