I just had this issue, and was able to resolve it by changing how location is handled.
It's definitely not the most private, but first you want to grant Google Play Services full location access all the time, then under Apps > Sandboxed Google Play, turn off "Reroute location requests to the OS"