I'm currently using the Mahdi ROM 2.9 build and GPS is working for me. I've also used the latest Dirty Unicorns build and AICP. GPS has been working for me.
It's weird. There are several people who have been having problems with GPS lately. I don't know if you use Xposed Frameworks. There's a module called Disable Location Permissions. I've used it. If you use that module, stop using it. Google's location permissions have changed. Plus, it allows you to remember the location settings so it won't show every time you turn on GPS.
You might want to upgrade your modem. In the last couple months, there was a problem with GS3 connecting to data. Not just Virgin Mobile GS3, but of all carriers. The solution was to upgrade the modem. Upgrading your modem might help GPS to work also.