See the bold text under "Guide". This scenario isn't valid anymore, it should now work for all GPS problems in custom ROMs without data loss.
I'm not responsible for data loss or anything you're doing wrong with your phone because of this guide.
@==vj== wrote that it is enough to just flash the NON-HLOS.bin, which makes sense, so you could try that first. Be sure to take the NON-HLOS.bin from a suitable image (GSM/CDMA) and check md5sum! If it works don't forget to thank ==vj==!
You can of course still follow the guide, it just takes more time though.
- Boot to recovery, make a nandroid backup
- (optional) Backup /sdcard, it will be deleted when you restore stock ROM!
- Pull the nandroid backup, remember, /sdcard will be wiped!
- Boot to fastboot (pressing Vol- while turning on the phone or type "adb reboot-bootloader"), restore stock ROM following this guide
- Install a GPS test tool like GPS Status & Toolbox, wait for GPS fix
- Reboot to fastboot again, flash a recovery, for example PhilZ recovery, by typing "fastboot flash recovery path_to_recovery.img"
- Boot to recovery and wipe data
- Install your custom ROM/GApps
- Boot into custom ROM and test GPS again, wait for the GPS fix
- Push backup back to phone
- Reboot to recovery, select custom restore and choose only data
- Wipe cache/dalvik
- Test GPS again, you should now get a fix
Hope this helps, ask me if you have questions.