The maps app is a bit wonky. The first few times I used it my gps icon stayed on forever and didn't turn off until I turned off location services. Then it couldn't find my location for the longest time (I had turned location back on). But I restarted my phone several times since I tried the app and now it works and locks on real fast. Maybe try that out?
Also FYI, if you Google an address on the browser and hit maps, the Web app is very good! Supports street view too. No voice navigation but very good for day to day use especially if you mostly walk or use public transport like me, and just want to get an idea of where you're headed.
Posted via CB10