Según tengo entendido todas las ROM de CM tiene problema con el GPS y se soluciona así:
Debes activar el modo "Opciones del desarrollado" y permitir ADB. Luego conectas el cable y sigues los siguientes comando:
adb reboot bootloader
fastboot erase modemst1
fastboot erase modemst2
fastboot reboot
Al menos así solucione yo el problema con una ROM basada en CM 12 (Android5.1.1)
PD: esta ROM es CM13 (android 6) pero imagino que debe ser lo mismo...
