Also die Beschreibung, wie ich es gemacht habe (im Endeffekt wie Neuinstallation)
Die Version die ich oben hatte war die 3.5.4. diese muss gelöscht werden (am besten über einstellungen->Anwendungen->Navigon... zuerst auf Daten löschen klicken (damits sicher weg ist) und dann auf Deinstallieren. Dann ist vom Datenspeicher mal alles weg.
Die version.xml war ja schon da, weil 3.5.4. diese einfach auf 3.5.0 ändern, der Rest kann ja bleiben (komplette Neuinstallation würde keine anderen ID's liefern). Sämtliche anderen Dateien und Ordner im Ordner Navigon löschen.
WICHTIG! und das findet ihr nur wenn ihr eingestellt habt, dass Dateien mit Punkt davor auch angezeigt werden sollen, oder ihr es auf dem PC auch eingestellt habt (seht ihr daran, dass ihr z.B. den Ordner .andoird_secure oder die Datei .Trashes seht)
Nachschauen obs auf dem Device einen Ordner (mit punkt davor!) namens .DeviceConfigurationBackupFile gibt, in welchem sich die Datei version_bkp befindet, deren Inhalt der selbe ist wie die version.xml (außer eventuell andere Versionsnummer) Diesen Ordner löschen (vorher sichern).
ansonsten wie gehabt (und von sprongebob schon vorher beschrieben):
3.5.0 installieren aber NICHT starten
mit Fresh die Karten ziehen -> am besten direkt phone an usb stöpseln anstatt Karte rausnehmen und über Kartenleser (machte bei mir immer Probleme)
auf 4.x übern Market updaten.