Ich hab mal etwas intensiver rumgesucht und es gab auch mit BQ oder Nexus Phones einige Leute mit einem ähnlichen Problem, GPS scheint unter Ubuntu Touch wohl noch etwas buggy zu sein.
Folgende Lösung hat bei mir schliesslich geholfen:
Darauf achten, dass der Nokia Next Standortservice aktiv ist (Systemeinstellungen->Sicherheit&Datenschutz->Standortzugriff). Am besten GPS anmachen und WLAN aus. Dann Phone neu starten und mit GPS verbinden (z.B. mit SensorStatus). Nach etwas Warten klappt dann die GPS-Verbindung. Es scheint beim aktuellen Softwarestand übrigens eine Rolle zu spielen, dass zuerst eine GPS Verbindung aufgebaut vor einer WLAN Verbindung.
Wenn ich die Schritte in dieser Reihenfolge gemacht habe, scheint es nach ein paar kurzen Tests auch anschliessend egal zu sein ob Here Service noch läuft, WLAN oder GPS an/aus gemacht wurde. Wenn ich GPS anmache funktioniert es direkt, gleiches für WLAN (mal abgesehn davon, dass es manchmal Probleme macht, wenn gleichzeitig eine WLAN- und eine Mobildatenverbindung aktiv ist, aber das scheint noch ein anderer Bug zu sein).
PS: Würde gerne den Entwickern Input zum Bugfixing liefern für diese Sachen. Wo kann ich das am besten tun? Bin ich hier richtig? https://launchpad.net/ubuntu/+source/indicator-location