I finally upgraded my Samsung Vibrant SGH-T959 to Firmware 2.2 build FROYO.UVKA6 only to find out that the GPS now almost never locks to a signal.
Downloaded an app called GpsRestore by Samsung Mobile. Launch the app.
Make sure you do this outdoors where the signal is strong otherwise, the app might not fix the problem at all -- you will see the app 'retrying' until it fixes the problem.
