A mi me pasaba lo mismo, lo que pasaba es que había que marcar la opción de ubicación y búsqueda de google siempre, y siempre te irá bien. O bien, reiniciarlo y marcarlo.
Depende de lo que quieras usar el maps o navigation. Si quieres que te dure un poco más la batería pues no lo marcas, si vas a usar mucho el maps o navigation pues lo dejas marcado siempre y siempre te funcionará.
Es un fallo que tiene. ESpero que lo arreglen con futuras actualizaciones.