First thing to do is check that the CPU fan starts up when you turn on the power of your PC. If that is the case, go into the BIOS and reduce the warning RPM level for the CPU fan. It may be set at 1200 RPM, but the actual RPM may be only 600 RPM. For safety, check your CPU temperature when idle, it should not be over 45° C.
Like Harm said, my p8p67 will do this if i set my potentiometer too low on the fan control on boot - the rpm isnt high enough for the mobo to say its working but i can reduce rpm it once windows is booted when im not doing much with the pc (for quietness), so i would check its running at all and what rpm in the bios.
Ok. I'm checking those things now.
Temperatures at idle are 34 - 41, depending on the core (the sixth one is always highest).
Today was atypical, in that the message didn't appear when starting the PC.
I'll try observerving the fans for movement, again tomorrow.
Right now both CPU fans are spinning.
I'll check the BIOS now, and see what the fan RPM warning level is currently set at.