I'm not sure if this will help a more savvy person, but it is, at least, on MY phone, something to do with LOCATION.
I have a Tmobile S5, with Tons of software apps (all from google store). I too have this problem BUT,
at Home and at Away locations ONLY. At work, no problem.
Work is Downtown...