Old thread, I know... but I just started experiencing this as well.
As of a few days ago, built-in Navigation app fails with "Data connection reset" (or maybe "Data connection lost"). I have rebooted phone, tried to get directions at different times of day, to and from different locations.
Steps to reproduce--
Start Navigation app. Enter destination. It shows map and my current (correct) GPS location in dimmed out map, while a "connecting" message appears on top. After about 60 seconds, voice says that data connection has been lost, and the spinner continues to spin indefinitely.
If I exit that screen and try again, I get same results. I use Navigation 2-3 times per day, and it has worked well for the past 2+ years. This problem is very new. I have killed app and restarted, and I have hard-reset device and tried as well. Same results each time. Phone has been rooted for 2+ years. I have not made any updates to the phone recently, and have not added any new apps. Based on the "data connection lost" message, it gives me the impression that the server side is hanging up on the request for directions. Or???