tl;dr – the fix for this problem is to go to your Google Apps admin console (admin.google.com), sign in if needed. Then, at the bottom of your dashboard, click More Controls > Apps > Additional Google Services. Then, remove the “featured” filter by clicking the X on the grey filter bar. Scroll down to Web History (yes, even though it’s prompting you about location history, it’s actually web history that’s to blame.) and turn that on for your domain.
I recently (in the past week) started having an issue with my Android phone wherein GMaps was convinced that my location history was off. It prompted me to turn it on and would not do any navigation until I turned it on, despite being able to find both me and the spots I was looking for without it. I could not figure out what was causing this issue, but Bing Maps navigation managed to work without it, so I just switched to that at the time.
If you clicked the message that said location history was off, it tried to open a webview that would fail to load. Since I couldn’t get that to load, I puttered over to my Android phone’s settings to look at location history settings. Sure enough, I found them and my phone said they were on both for Maps and generally. So, wtf.
The culprit, I figured, could have been a Google Maps update or a recent Android update on my Moto X to 4.4.4. Yet, searching for location history issues associated with all of those things came up fruitless. I did eventually find some old issues (2013 or earlier) that others using Google Apps For Your Domain (GAFYD) aka Google Apps for Business aka Google Apps for Work were encountering. I’m a GAFYD user, grandfathered in for free from long ago. So, easy peasy, I should be able to switch to my non-GAFYD account in Maps and resolve, right? No dice. Because my primary Android login is my GAFYD account, it wouldn’t let me switch permanently, so I didn’t consider that a real fix.
Yesterday, I finally got the link to load. Turns out it was taking you to Google’s History settings webpage, which I only peripherally knew existed. That page showed a web history setting to share my Chrome web history to improve my device. Sure, go for it. (I don’t use Chrome on desktop or mobile. Firefox all the way, baby!) On that page, it wouldn’t let me change it because “Based on your organization’s current settings, this feature is disabled. If your administrator changes this in the future, your choice here will be honored.” ::sigh:: But at least this gave me a specific error to search. Searching for that error was fruitless, though. Since the page talked about web history, though, it gave me the idea to search for that along with GAFYD and all its names through history, which eventually led me to this page and a solution. The instructions on that page are actually out of date, though, so scroll back up to the tl;dr at the top of this page for updated instructions on how to resolve this pesky and poorly explained error in Google Maps for Android.
Then, once you’re done, contemplate why Google has decided to block you from using navigation (which doesn’t need your web history) until you turn on web history. From reading some other things, I suspect that it’s because Google is trying to use your web history to make its location searches more accurate and enable voice searching features, which is a good thing to do. However, cutting off access to an unrelated service to force customers into allowing that setting is a major dick move. My guess is that the business case for the searching features (which is probably based on selling advertising targeted by location) demanded that they get high compliance, and so they held navigation hostage in order to do so.