Fiz a atualização para a versão 3.9.7.0 e meu celular com Android 5.1 MOTO G. E agora quando tento iniciar o aplicativo aparacere a mensagem que não consegue fazer conexão. Na versão anterior não havia problema.
Alguém tem alguma informação para resolver este problema.
Tenho três Moto G 2ª Geração com Android 5.1 que estão funcionando normalmente com a nova versão.
Tente reinstalar em uma conexão estável (WiFi).
O meu é um Sony Xperia Z3 dual e tá funcionando sem problemas, só não sei oque mudou com essa atualização
O meu é Moto G (3ª Geração), Android 5.1.1 funcionando normalmente. 
O meu também estava com problemas na nova versão. Acabei desinstalando e limpando todos os dados do Waze e retornei para a versão 3.9.6.101