Es que si estas usando el navegador que viene en el movil, el de google maps, ese necesita SIEMPRE la conexion de datos para descargar los mapas, ya que no los almacena en el telefono. Quizas tu problema era que sí tenia señal de GPS y lo que no tenia eran los mapas porque al no tener conexion de datos, no se estaban descargando...
Hay varios navegadores para descargar en la zona de software del foro, yo uso Navigon y es muy sencillo y no falla nunca, el sygic tambien me funciona bien. Con estos te descargas los mapas en la tarjeta SD y no encesitas nunca conexion de datos ;)