Yea, you can def do a manual install to see if it will help. I've had strange GPS behavior in the past - sometimes it's a bad flash, sometimes the radio goes to the dumper.

I'd look for a cab to manually install QGPS. If that doesn't work, it sounds like you already tried switching your radio [even if you have the latest and greatest, sometimes swicthing up can make a huge difference]. The last troubleshoot would be to flash back to a stock ROM and check your GPS connectivity there. If you're all good, flash back to the custom ROM...if your GPS dies again, well...well, then we'll keep thinking of other options.

Good luck.