Here's what I did to troubleshooting Google Maps
1. Go to Settings -> Location, disable. Restart phone.
2. Open Maps; it will prompt you to turn on "Location", say yes.
3. Go to Settings -> Location, optimize settings (or in Maps -> Settings)
4. In Settings, go to Maps, clear cache, then...