Apparently this has some thing to do with the Auto Start Manager in the Mobile Manager on Asus Zenphones.
I'm not entirely sure what I did, I did a lot of things, but it seems to be working now.
Start Mobile Manager, Go to PowerMaster, and then Auto Start manager. Then I'm not really sure what I did specifically to make it work. I disabled all of the apps in one of the sections, may have restarted, re-enabled the apps, may have restarted again. At any rate, it started working after I fiddled with this.
In case someone with an Asus phone runs into this issue, hopefully something here will lead you in the right direction.
Seems strange, but it worked for me.
I think it was preventing something that Google Play needs from auto starting and flipping the switch on and off reset this. But unfortunately I can't give you any more specifics.
Hope this helps someone.