yo me encontraba en un caso similar al tuyo, haciendo pruebas creo que ocurría cuando la señal gps bajaba de un mínimo. y además ocurría desde que el móvil pasó a
froyo.
lo solucioné pues dejando de usar
andando aunque me dió bastante rabia por ser desarrollo del grande
javielinux.
ahora uso
oruxmaps, un desarrollo de otro español, más completo pero también mucho más complejo. hasta la fecha no tuve problemas.