Check carefully how the new fan is plugged in. First, verify that it is lined up with the right pins. It should only fit on the mobo 4-pin header one way because of the plastic tongue sticking up next to the first 3 pins of the mobo header. If that's OK, try unplugging it and re-connecting it a couple of times. Also inspect the fan to be sure its wiring is OK. If possible, test the new fan by supplying a 12 VDC supply to its connector holes. If you don't have a handy PC with a free mobo fan header to use, a car battery and some wires will do. The car battery is 12 VDC. On the fan's female 3-pin connector, Pin #1 will have a BLACK lead to it, and that is Ground (battery -). Pin #2 will have a RED lead to it, and that is for +12 VDC. If you apply the battery voltage to those contacts, the fan should spin immediately and easily.
I suggest these things because the symptoms you cite look very much as if the mobo is NOT detecting any speed signal coming back from the new fan. Every fan generates a speed pulse signal that it sends back to the mobo on Pin #3 of its connector (Yellow wire). Although this signal is not used for control of fan speed, it is how the mobo can measure and display the fan's speed. In the particular case of the CPU cooler fan, MANY mobos also do extra work to monitor that fan for failure. If the CPU_FAN header fails to receive a speed signal (either because the fan actually is not turning, or because the signal connection is poor), it assumes the fan has failed,. It issues a warning you can see for a few seconds, then completely shuts down to protect the CPU from disastrous overheating. It does not wait for the temperature sensor inside the CPU chip to send out a high temperature signal. And that's what your description sounds like.