Google Maps Fehler bei der Routenberechnung

Hallo zusammen, hoffentlich kann mir jemand helfen.
Auf meinem Android Smartphone lässt sich die Google Maps App zwar öffnen und ich kann auch nach Orten suchen, allerdings funktioniert die Routenberechnung dann nicht.
Habe das neueste Update runtergeladen, den Cache und die App-Daten gelöscht und es geht trotzdem nicht. Mein nächster Lösungsansatz wäre es gewesen, die App komplett runterzuschmeißen und nochmal zu installieren, allerdings funktioniert das auf meinem Huawei P9 lite nicht, da die App als Standard installiert war („Systemandwendung, Deinstallation nicht möglich“).
Die Fehlermeldung die ich in der App bekomme lautet folgendermaßen: „Verbindung zu Google Maps kann nicht hergestellt werden. Bitte versuche es in einigen Minuten erneut.“
Das Problem besteht jetzt aber schon seit einigen Tagen.

Danke schon mal im Voraus!

An einem Update kann es nicht liegen. Bei mir wird nichts automatisch aktualisiert und ich habe auch manuell kein Update installiert.

GPS ist auch eingeschaltet, daran kann es eigentlich auch nicht liegen, außer die App verarbeitet das nicht richtig. Was aber auch komisch wäre, da das ganze ja vom einen auf den anderen Tag so war, ohne Update dazwischen.