Bueno, investigando por ahí, encontré un navegador GPS que sirve casi para cualquier teléfono que pueda compilar JAVA.
Se trata del software NAVIGON MN6.
La única putada es que tienes los mapas en web y los vas descargando vía GPRS. Ahora mismo estoy bajándome unos mapas que ví en el ares y a ver si de alguna manera cargándolos en una tarjeta de memoria, puedo hacerlos funcionar en mi Z300.
Con esto, las posibilidades de cualquier móvil que tenga VM de java tiene unas posibilidades cuasi infinitas ya.
Un saludo!