Go to market and download GPS Restore app for Samsung. Then go outside where you have open sky and run the app. It may not be able to see any satellite the first or second time, but keep trying and eventually it will work. Once it's done, your GPS should be okay, although it still takes a little bit longer to get a GPS lock vs. other phones and the accuracy proximity is quite large.
