OK, you didn't mention what actaul cpu you have. If this is AMD type, they don't last long when the fan fails. They either degrade or simply fry, thus won't work well. Even, if the bios setting for "over temp" is correct and reached and starts the reboot or shutdown procedure, with AMD it maybe too late. Now, if this is an Intel P4 cpu, it's more robust and should either shutdown on its own or with bios start to shutdown. That doesn't mean if the fan failed entirely or stopped for whatever reason it can always recover, it too can be damaged. Take a small household fan(on high) and blow it across the cpu and then turn on system, does it try to work longer? Or does it fail outright again., if so maybe damage is too far gone. Hopefully, only the cpu needs replacement, but hi-temp damage to mtrbd. possible, if you see browning or brittle looking mtrbd. Overall, its not good.
Don't discount any other source heat build-up maybe the power supply is kaput or something else is at fault. Excessive heat takes its toll on any componet, so check it out.
good luck
-----Willy
I just replaced my CPU fan last week and put in a new hard drive. This morning the computer was off. Turned itself off. Don't know when. It was very hot. Turned it on to see if it was a fan. Before I could find out it turned itself off again. Now it will not come on at all. Do I need to take it in for repair or do I need to repace my motherboard?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic