The problem is probably this: you have the CPU fan plugged into the wrong connector or you have a cheap aftermarket CPU fan.
If you are using the heatsink/fan that came w/ the processor then you're fine. My A8N-SLI does the same thing. Don't worry about. Disable the warning message.
If you really really really want to be sure nothing's wrong, run Ai Booster (you should have installed it, if not it's on the Asus mobo CD) and check ur CPU temp. It should be at/around or below 45C for that processor. Assuming you have a decent case w/ decent airflow... You can also check the CPU temp in the BIOS.
If you've got fan speed control set/cool and quiet or similar then that's probably the cause.
The BIOS is probably set to only turn on the CPU fan above (say) 20 degrees .. when you turn on the PC the CPU is cool so the fan is off and it triggers the alarm. The CPU quickly heats up so the fan starts... It's probably not a problem.