Der Stick kann kein LTE. Derzeit werden bei O2 und Vodafone massiv UMTS-Masten ab-/umgebaut, um die Frequenzen für LTE freizuschaufeln. Und selbst wenn dein Stick von UMTS auf Edge zurückfällt, dann kann es sein, dass per Edge einfach zu wenig Bytes übertragen werden und die Timeouts das Navi zu Fehlermeldungen verleiten.
Eventuelle Zwischenlösung: keine Ahnung wie weit in deiner Region derzeit die Verschmelzung von E+ und O2 vorangeschritten ist. Vor einigen Monaten mussten man Roaming aktivieren, damit Handys beide Masten nutzen können, die ja inzwischen zu einem Konzern gehören.