Yo tenia el mismo problema hasta hoy.
Tienes que dejar que google obtenga permiso de tu ubicacion en las aplicaciones.
Eso tienes que activarlo creo desde el google maps. a mi me ha saltado una ventana hoy, y tras darle a aceptar ya me ubica el navigation. fijate que casualidad.
