Apparently the Galaxy S3 is notorious for GPS issues, and those issues have an easy fix: Tighten the screws on the back.

http://forum.xda-developers.com/showthread.php?t=2201668