I had this exact problem and none of the suggested solutions worked. I also have had my Galaxy S5 less than a week. I fixed it by going into settings then app manager then all the way to the last heading, "turned off". I went through that list and turned on anything that appeared necessary, in my case Samsung Galaxy. So if it said Samsung, android or galaxy I figured it should be on. That fixed it the message went away. I had downloaded an app manager that put several things onto the sd card to clear out the device so I think somehow it turned things off rather than moving them.
Good luck, I hope this helps.