I'm also having the same problem. Maybe I'm being stupid but when I pick a location on maps and hit the second tab that usually gives me the option for navigation or directions it goes straight to directions. GPS and all location services are on (if someone could explain the difference between the three location services, I'd appreciate it)
Mine just started working again this morning, not sure what happened. Was a little worried that maybe vzn blocked it to force the use of vz navigator....
There was a thread a while ago, maybe this should be made sticky?
You should close both Navi and Maps, then just open Maps and wait for your location to register. Then close map and open Navi and it should pick up within a minute.