Before doing anything try a factory reset from settings and see if that helps you, or even use odin and go back to stock and factory reset from settings. Proceed if you still have problems.
Also note that some users report that clearing agps data can solve the problem.
I AM NOT RESPONSIBLE FOR YOUR PHONE!
[With no GPS icon showing up]
(OPTIONAL AND RECOMMENDED: USE Triangle Away to reset counter)
1. Flash back to stock UNROOTED ICS ROM
(Stuck at samsung logo after? flash a cwm recovery, factory reset and clear cache n reboot)
2. Enter into dialer *2767*3855# (Will do a HARD reset, no internal storage will be lost except the usual data)
3. Boot up again and run maps to see if you have a GPS icon
(IF YOU DON NOT HAVE A GPS ICON YOUR HARDWARE IS MALFUNCTIONING)
[With GPS icon showing but no lock]
4. Turn all GPS related thing OFF
5. go into google services framework in applications, settings, and clear data
6. go into maps, delete updates if any and clear data aswell
7. reboot the phone
8. Update google maps (very important)
9.reboot for safe measure
10. turn on everything in location and services in settings
11. boot up maps
[If GPS is still flashing but no lock]
1. If steps1-11 does not work for you it is highly recommended to flash Galaxy S III Test 3 (created by crypted)
2. Factory reset trough settings and repeat steps 1-3 if not gps icon or steps 4-11 if gps icon flashes
For flashing new ROMs after:
1. see if gps is showing up or not, if not then repeat steps 1-12 above and it is recommended not to flash the same rom that makes gps disappear
2. if gps icon is showing up but very inaccurate then repeat steps 4-11
Sometimes I noticed esp. on AOKP n CM10 n Paranoid if you just simple delete and reinstall a new maps it works (with gos icon showing ofc.
Some people asked about if mobile odin is usable when going back to stock, and yeah it is just be safe doing it and make sure it is the whole package.
Want a faster lock after? go here
Thanks to crypted for his aGPS work.