Check your system and CPU temps by entering the BIOS and looking at PC Health. Or you can download a utility to show the temps while in Windows. One such utility is speedfan. Download from the link below.
I think you need to replace your fan but check the temps. I suspect the fan must rotate at a minimum speed or the warning is shown. click here