I have a Galaxy S4 and have only had it since October 20, 2015, and I was on my phone when it suddenly restarted itself without asking me. When it came back on the error message that is my title appeared. I can't go on Google Play Store anymore. I had wanted to update an app cause it won't let me play unless I do so. The message reappears very often, almost every 5 secs. I've tried uninstalling updates, deleting cache and data on both Play Services and Play Store, as well as force stopping them, going into recovery mode and clearing cache partition, and resetting app preferences. I really wish I don't have to reset back to factory settings because I don't know how to backup my phone to anything and really don't want to lose anything on my phone.
Update: I have tried getting a rid of cache on Google Framework and installing an updated version of Google Play Services.
P.S. Is there someone I can get in contact with if this doesn't stop? Preferably an email, but if not a store. Thanks!!