If it was working fine up until then, then it's probably a bug someone introduced. Complain, wait until they get it fixed. Since you got it from Verizon, I would complain to Verizon. Since you got the update from Google, I would complain to Google.
Also, couldn't hurt to run some diagnostics. Maybe the GPS unit in S3's are prone to failure? Did you see that page where a girl and her boyfriend got the exact same phone at the exact same time, and his still works, and hers doesn't?