I have Galaxy S3 for 3 months now, first month and half phone worked great. last 45 days or so can't find my location when using google maps, accu weather, navigation etc. GPS is on.
Happens to me sumtimes, I just input my location into the accuweather and it works...never had issues with the others but are you outside? maybe go away from buildings that may restrict you getting signal? Happened to a friend of mine when he used a new case strange but yea...so maybe go outside an see if it helps or take off your case...