Heureka!
Meine Vermutung, dass es evtl. etwas mit einer schlechten Implementierung der Google Applikationen zu tun hat, scheint sich bewahrheitet zu haben. Sowohl die 'DB Navigator' App als auch die 'Aral' App funktionieren jetzt!
Mein Kalender-Sync-Problem konnte ich ja bereits mit der Installation der 'GoogleCalendarSyncAdapter.apk' aus den aktuellen GApps lösen. Also kam mir die Idee, die kompletten GApps zu installieren. Einzeln kopieren und dann noch die Permissions anpassen war mir zu aufwendig, also habe ich versucht die GApps (gapps-jb-20130812-signed.zip) zu flashen. Das funktionierte mit der Stock Recovery allerdings nicht: 'Installation aborted'. Scheint wohl nur über eine CWM Recovery zu funktioneren...
Gesagt getan. User 'tommy0815' hat ja dieses Wahnsinns Root-Tutorial geschrieben, mit dessen Hilfe ich ein CWM Recovery erstellen und aufs Handy flashen konnte. Damit klappte das Flashen der GApps dann problemlos.
Dann noch die Anmeldung im PlayStore und siehe da, keine Inkompatibilitäts-Meldung mehr und die Installation klappte auch. Nur Navigon geht immer noch nicht...