I've been able to temp fix it by going into Settings, Location, Maps, and toggling Location Services and Location History off and on (with a reboot for good measure), but it's super-annoying and I can't pinpoint when it will work properly and when it won't. Sometimes it works just fine in the morning but quits working properly in the evening of the same day. No changes made in the interim that might cause it.
Anyone see this and know a fix? I'm on Mahdi ROM latest version with latest version of Maps. Maps version doesn't seem to matter, it happened on an older version and then the most recent version again this evening.