It's not just my phone, it's both mine and my fiancées AT&T GS3's both that it happens to. I've posted in a few threads and gotten nowhere with it on both of our phones. Started shortly after we did the JB OTA. She has a case, I don't have a case.
Tried a variety of things posted around the web. Tightening screws, reinstalling maps, clearing data, NV rebuild, resetting to stock JB. The NV rebuild seems to work the longest. Eventually it gets to a few days of usage and the GPS icon stops showing up and Google Maps navigation doesn't work anymore. If the phone is rebooted, it comes back but will got out randomly (generally at the worst time - while you're lost somewhere, that's how these things work apparently).
Neither of our phones are rooted or have ever had anything flashed but stock ICS and stock JB.
Dude, I don't know what to say. I know the OP works from first hand experience but your phone might still be messed internally or you are making small mistakes from the OP. I'm sorry bud but I'm not Samsung, I don't think I can help you any more