I hope this will work for you. This worked for me. I don't pretend to understand all the details of what went wrong, but from what I understand there's a non-volatile (ie factory reset, reboot, etc won't fix it) privacy setting on the GPS which, when activated, basically breaks GPS. Samsung must have realized this was stupid too because the latest stock rom/modem doesn't mess with this setting anymore. Unfortunately, if it was set before you upgraded to the newest modem, that means your GPS is stuck in privacy, aka non-working mode (stupid because if you didn't want GPS you should just turn it off).
So what you need to do is backtrack to a combination of software that DOES mess with this setting. Once you are SURE GPS is working again, you can consider flashing the new stuff again (you may have to try more than once because there is absolutely no user control of the privacy setting, another stupidity in the system).
So
1. Flash either an older stock image (newer stock image contains the same privacy bug so you can't use that) or older cyanogenmod and modem. For stock, I recommend the original firmware released with the phone
https://dl.dropboxusercontent.com/u/103520801/T699UVALH1_T699TMBALH1_T699UVALH1_HOME.tar.rar
That is what fixed mine
You can try the following version of cyanogenmod + modem
http://goo.im/devs/nardholio/apexqtmo/cm-10.1-20130309-UNOFFICIAL-apexqtmo.zip
https://dl.dropboxusercontent.com/u/103520801/RelayLJ1modem.zip
2. Do a battery pull and wait a minute. Just to clear out anything that might be lingering.
3. Obtain a solid GPS fix. Install GPS Status and stand outside. If GPS doesn't come back at this point try the other route (cyanogenmod or stock)
4. Turn off GPS.
5. Battery pull, do not power off
6. Flash forward to cyanogenmod (build 111 or higher)/newer modem. You can try restoring your nandroid (at this point mine worked with a restored nandroid) but if GPS goes away again try with a fresh install.
7. If you obtained GPS on stock but cannot get GPS going in cyanogenmod try repeating again but replace step 4 with "do battery pull while you have a solid gps fix"