This is really annoying. I search for something and it just says "searching" forever. I restarted the phone same result. I really need this to work because I'm out of state and have no navigation!
Is this on WiFi or on the cellular network? Can you use other apps that require a data connection? Try going to settings > applications > Google Maps > clear cache and settings.
