try this:
on dialer, dial *#9090#
you will see a service menu
press on top right corner, "enter key input", press insert 'Q', then press ok
"enter key input" again, press 0000, and press ok
wait for few seconds, up to 10 seconds
you will now see a secret service menu
now, go to UTMS -> COMMON -> NV_REBUILD -> NV_REBUILD -> SYSTEM,PROTOCOL,GPS,IMS
Reboot your phone, try GPS again with GPS Test app.
this will force the software to clear cache and rebuild the software from the original code, sorta like a 'flush all the clogs in the software' feature. It will not cause any loss on user setting, files, apps and is not a hard reset.
My Note 3 running on custom firmware also faced a similar issue, and I knew for sure it's a software problem, and this helped me getting back my GPS signal back, a very strong one I must add, accuracy highest at 3meters, and averages around 10-13meters range
The secret service menu doesn't pop up after I key in "Q" and then "0000". Is it locked or something or only works on specific devices?
The secret menu never comes out now matter I try with "QO", "Q0000" or "Q" then "0000".
EDIT: Rooted my phone and installed the "Phone info Samsung" apps. Managed to access to the secret service menu through the app and found NV Rebuild. Did that and it didn't help on the GPS issue