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...