There's another possibility. You say the fan actually is working. Are you sure, and are you sure that it is turning fairly quickly?
If yes, here are two things to check. The reason for that error message and shut-down is that the fan's speed signal (on Pin #3 of the fan header) is not reaching the mobo, so it thinks the fan is not turning. As a protection, the system shuts down completely right away to avoid CPU overheating, even though the actual temperature sensor inside the CPU chip has not signaled a high temp.
This can happen either because the wiring for that signal, from the fan to the connector on the end of its cable, is faulty or disconnected. So, inspect for broken or poor connections in the wire and connector.
It can happen also if the connector and the mobo header pins have a little bit of oxidation (corrosion) of the metal, causing poor contact between them. The simplest thing to try is this. Carefully unplug the fan connector from the mobo header, them plug it in again. Do this several times. This action may "scrub" the metal surfaces clean and re-establish the connection. After doing this, look around carefully and verify that you did not loosen some other connector by accident. Then close up and see if the system works.
You can combine both of these into one operation - disconnect and inspect for loose connections, then do the plug / unplug / replug thing.