cpufan does not function correctly

I've been getting the above message intermittently on boot - it beeps a whole lot and automatically shuts down. After cleaning it and making sure no wires were catching in it or anything, I ordered a new fan, installed it and booted again. I can hear it working, and it certainly sounds a lot better, but the BIOS still bitches and refuses to boot. Oh and it's no longer intermittent; it's every time now. Google only returns one hit, and following it gives me a good old 404. Ideas?

Dance around the computer naked while chanting Celtic chants, then pray to the 7 sins, the devil and sacrifice a virgin.
After that preperation is done, clear the CMOS and start computer again.

If this fails you need professional computer exorcism or through testing of every piece of hardware on it. Also you might wanna check your computer manual for the code it beeps.

is your new fan an expensive one, that's not stock? Sometimes those also cause the same problem as broken default fans because they are slower if the CPU is cool, you gotta turn some cpu fan warning stuff off in the bios.

Also you might wanna check your computer manual for the code it beeps
No code, it just beeps like crazy until it turns itself off. I'll try clearing the CMOS though if I can figure out how.

is your new fan an expensive one, that's not stock?
Nope, cheap one off ebay.

Update: clearing CMOS did not fix it. This fucking sucks, I hate PCs.

Can you get into your bios with the old fan? If so, there might be a setting to turn of fan warnings.