Anyway, this morning I installed "AppOps" from the App Store. It's the one by Sylvain Galand, and the package is fr.slvn.appops. It doesn't need root, apparently. I used that to disable location access from both UP and MyFitnessPal. Since then, my GPS has been working fine again.
I think there's something broken under the LocationManager implementation in this version of Cyanogen. Seems like some apps are able to break it somehow. The other thread about this subject points fingers at Dragon Dictate, too. Whatever it is, apps shouldn't be able to wedge a system service like this.