Well, it seems that your location fix isnt really working as intended. Now we have to see why.
Please recheck your Location Settings, how are they setup? Go to Settings > Location and check. Try to set to high-accuracy and test again. You need a working internet-connection too to fully make use of this though. And of course, make sure that GPS is turned on, but i probably wont have to tell you that
As a good alternative, depending on size of city at least, is to store the map on local storage. Maps has an option for this. There you can select an area to be accessable without Internet connection, maybe try to use that and see if it works better.