Try this (no guarantee that it will fix the problem):
Open the Phone, as if you were going to make a phone call and dial -
*#9090# -- Diagnostic Configuration (*#197328640# if that doesn't work)
Menu, select Key Input, enter Q
Menu, select Key Input, enter 0000
Wait for the next menu. (It takes a while.)
UMTS->COMMON->NV REBUILD->NV REBUILD->SYSTEM->PROTOCOL->GPS->IMS
or, if you don't have UMTS:
UE SETTINGS & INFO->SETTING->SYSTEM->NV REBUILD->ALL
Restart the phone.
The initial GPS fix could take a long time if you're moving, bur subsequent fixes take about 3 seconds.
GPS Status & Toolbox will show you what's happening with the GPS receiver. (You have to have Location set to high accuracy for GPS to be running.)