Maps finden kein GPS, Fix habe ich aber!

Hey,

das Gerät:
Galaxy S4 LTE-A i9506
CM12.1 Temasek

Problem:
Manche Apps finden kein GPS Signal. Wenn ich auf "Hohe Genauigkeit" gehe, wird eine "ungefähre Position" gefunden

Apps:
Maps: Findet nur mit "Hohe Genauigkeit" eine ungefähre Position. Beim Navigieren hüpft es immer hin & her
Pokemon: Findet nur mit "Hohe Genauigkeit" eine ungefähre Position. Beim Navigieren hüpft es immer hin & her
Navigon: Findet auf "Hohe Genauigkeit" und auf "Nur Gerät" schnell eine Position und die passt auch

Was ich versucht habe:
-Faster GPS installiert und meine Region angegeben
-Die Datei gps.conf durch eine von hier ersetzt
-Cache bei Maps, Pokemon, Play Dienste gelöscht
-Die letzte CM12.1 Snapshot verwendet
-Handy zig mal neugestartet

Was mir noch aufgefallen ist:
Die App GPS Test findet nach 10sec. einen "2D Fix" und nach 20sec. einen "3D Fix" und die Koordinaten die angezeigt werden stimmen auch.

Jemand eine Idee?