How to re-enable Location service access for Google apps on my phone?

[RonanTheGrey]

My problem is this: No Google apps on my phone are able to access GPS. Period. No matter how many times I say "Yes" on this stupid dialog: http://take.ms/SXmxg

I have searched the internet for almost 2 months looking for a solution to this. I have visited every Google account & history management page and enabled every setting I can find even ones I know aren't related. I have uninstalled all updates to Google Play Services and Google Now and re-installed them, and disabled and re-enabled Location via the toggle, more times I can count.

Nothing I have searched for, and nothing I have done, works.

This all started at the end of February when Google released the latest version of Google Play services. It broke something on my phone that now seemingly cannot be fixed. I cannot use Maps. I cannot use Uber. I cannot get directions. I'm beyond frustrated.

Has anyone run into this before, and have any idea how to fix it? The last resort, which I have not done, is completely wipe my phone and start over but honestly I have no confidence even that will fix it.

My phone info:
Sony Xperia M4 Aqua E2306
Android 5.0
Google Play services 8.7.03 (2645110-246)
Google App 5.12.34.21.arm64
Google Maps 9.25.1

Hope that's enough. Thanks for any help.

 

[N4Newbie]

What do you see when you go to Settings -> Location?

 

[RonanTheGrey]

Hi there, thanks for replying, sorry the delay over the weekend... here is my Settings -> Location screen:

 

[N4Newbie]

Can you please go to Settings -> Apps -> Google Play Services -> Permissions and ensure that every listed option is enabled? On my Nexus 6P, they are:

Body Sensors
Calendar
Camera
Contacts
Location
Microphone
Phone
SMS
Storage