I had an issue with a previous computer which was running genuine Windows where I received a similar message all of a sudden. It looked legitimate and after checking for virus' and spyware, I ended up going to the Microsoft website and running the validation tool which fixed the problem. Might be worth a try.
Go to http://windows.microsoft.com/en-AU/windows/genuine and click the Validate Now button at the bottom of the page. If it comes back as validated you know your OS is ok.

Can you post a screen shot of the offending message?

I would try scanning with a different antivirus and spyware program. Avast have their 2015 antivirus for free (www.avast.com) which I've found to be reliable.