Does it give the message in windows or at the POST screen
Is this a recent problem? If so, you may have just changed some settings. I'd recommend a system restore in this scenario.
If not, try the keyboard in another computer just to make sure that it is actually the computer! If it works in another computer and the system restore doesn't work, then you probably have a faulty keyboard now..
Bad USB port maybe?
Again keyboard works fine after boot-up
Have you got enable USB keyboard support in the bios, if you dont a usb keyboard wont work in the bios, only in windows. If you can get a PS/2 keyboard go into the bios, enable USB keyboard support, shut down, hook up USB keyboard and reboot, the message should go away!