Assuming it's a Samsung phone:
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.
Run
GPS Status & Toolbox to see what the GPS receiver is doing - Maps is just a consumer, if it's not working it might look as if the GPS isn't working.