I am still getting a message saying that the CPU fan has failed. But I can see it spinning in the case. Also, the report from sensors shows everything running at perfectly normal temperatures.

Kind of a shot in the dark here.
Is the fan one that has a sensor lead?
That is usually a 3 or 4 wire fan control.

If that is the case and the fan bearing is shot or gummed up it may not be able to spin fast enough for the bios.
Try replacing the fan if you can.

-- 
Alvin Starr                   ||   land:  (647)478-6285
Netvel Inc.                   ||   Cell:  (416)806-0133
alvin@netvel.net              ||