Welcome to Tom's Hardware Forums,
You can sometimes get that message if your fan(s) do not come to speed (during POST they are ramped up briefly) when expected. You usually will only get that message during a cold start if that is the case. Restarts probably will not result in that message since the fan does not (usually) stop during the restart process.
If you do get that message during restarts, let me know, it may be another issue completely.
Hope it helps