i had the same issue, i fixed it by replacing "gps.*** " ummm, i dont exactly remember the name of file or the exact path, but you should be able to find it in system partition.
somewhere on these forums there is a list of different gps files for almost every country, find and download the one for your country or neighbor country.
just google for "replace gps file for fixing gps on android"
and find it
Sent from my iPhone using Tapatalk