I'm having the same issue...I tried the reset apps fix....I'm still getting the error message. When I do, I lose the internet connection. The only thing that will get it back is to restart the phone.
This weekend, I'm going to do a factory reset and install one app at a time...I've already uninstalled a lot of stuff I don't really use.
Driving me crazy!!!
Sprint GSIII 4.1.2