Check carefully the way your CPU cooling fan is plugged in. It MUST be plugged into the CPU_FAN header. MANY mobos (I can't be sure about yours) monitor the fan speed on the CPU_FAN header carefully to detect failure. If the header fails to receive a fan speed signal (via Pin #3 of the header) from the fan, it will trigger an alarm condition. On many mobos, the resulting action is first to send out an alarm (beeps plus a screen message) and shortly thereafter completely shut down the system. This is extra caution to prevent overheating damage to the CPU due to lack of cooling, and this protection system does NOT wait for the temperature sensor inside the CPU to register high temperatures.
What you describe may well be because the system has not received a good fan speed signal on the CPU_FAN header, and is following that protective action path. If that is happening, either the fan is not sending a signal, the fan wiring is faulty and not delivering the signal to the header, or the mobo header is faulty and not registering the signal. Since you are sure the fan actually is working, you can try this temporary test procedure to try to narrow down the problem. With the system off, exchange the fan plugs from the CPU cooler and one of your case vent fans. Just switch the plugs for those two. Now start up and observe. The fans all should start up as normal. But then, does the system keep going, or fail again the same way?
If the system keeps going under this configuration, then the CPU_FAN header is actually getting a good speed signal (from the wrong fan, of course!) and there is no error condition there. In that case, if you check the speed of the fan plugged into the SYS_FAN header where your put the CPU fan temporarily, see if its speed is zero. If so, you know the fan is sending a bad signal.
If the system fails just like before in this test configuration, then maybe the mobo CPU_FAN header is faulty.
With fans actually working, you can let it run for a few minutes to be sure of the result. Then shut down and re-connect the fans properly.