Since my GNex updated to 4.2.1, I have been unable to use Navigation. The GPS works fine in maps, but I get "waiting for location" endlessly in navigation.
Try clearing the cache of the navigation app. Do you have any other apps that use GPS that can confirm that your radio is causing the problems and not just the app?
I don't have the navigation app on my app list. I have maps but no navigation app. Is it under a different name or something? And I did go to all apps and not just downloaded.
The navigation app should still be in your app list. All that I can suggest is going outside in the open, outside of the car, and trying to get a lock.