I'm having the same problem on 3 different phones.
Note 5 and another Note on Verizon, Galaxy s6 Edge Plus on Straight Talk. Happens on wifi or cell data.
I have done the following:
Disabled Google apps, reinstalled factory version, and sideloaded a prior apk from a friend.
Shut down, went...