I occasionally experience that on a couple of devices - though I don't have a Sammy - but find that it can be fixed by toggling Mobile Data off and on, or doing the same with Airplane Mode or Wifi. On the other hand this occurs when I actually am offline. In your case, perhaps it occurs when there is a brief signal drop that you are unaware of, but which triggers that response from the phone? Signal can be checked in Battery Usage....touch the graph to open it and see if there are any red lines.
I have an S4 (regular) and I have the same issue. It's been happening for a few months.
Once I'm off Wifi and on mobile, I frequently run into "offline" problems with all Google products (Gmail, play store, music, youtube, Google Maps, etc). It will frequently be offline and have syncing issues with all Google products. Seems to have some delay for syncing. Always in a 4G signal area and don't have issues with connectivity. I can stream YouTube no problem, but when I swipe to the left to look at my account, it has problems.
When I look at the Google Accounts screen, I have sync errors.