Apps keep asking to turn on GPS despite being on

[gymnophoria]

In various apps that reply on location I keep getting the message "To continue let your device turn on location using Google's Location Service. Your device will need to: Use GPS".

Now: location service is switched on in settings, and I prefer to use battery-saving wifi and mobile networks except for the rare occasions when I need pinpoint accuracy. I've also checked permissions for all apps involved, nowhere is location permissions switched off so far as I can see.

The Maps app seems to know where I am, and if I look at Google's uber-creepy location history, it shows exactly where I've been.

Any ideas? I have a Oneplus One running Android 6.0.1, Cyanogenmod 13.