Can you see the CPU tempurature in the BIOS menu? Probably won't help much, since the CPU isn't stressed while in the BIOS setup, but if this happens during bootup you might be able to see something. There are some CPU temp monitor programs out that that overclockers use, it might be worthwhile to download one of those to check your temps while under load. Maybe the error you see is misleading, the PC sees a high CPU temp and assumes that the (nonexistant) fan is dead. If the CPU is running hot, maybe the heat sink needs to be re-seated with new thermal grease.