A qué te refieres con "entrar en navegación"?
Y en cuanto a permisos, los Servicios de Google Play tienen acceso a ubicación? (es una pregunta un poco estúpida porque los Servicios de Google Play son los que te proporcionan la ubicación, pero por si acaso...).
Te diría que mires el archivo gps.conf pero si llevas ROM global estable deduzco que no tienes root no?