This really works!!!! After months and months of this annoying message on my phone and trying all the suggestions I finally decided to run a software update and it worked!!! I just tried it and it honestly worked. You need to look for "About Device" on your android phone and from there you'll find the option for software update. You will not loose any of your data and contacts.
Please do let me know if this works for you....
— modified on Oct 19, 2014, 8:55:47 PM