Para los Galaxy muy antiguos igual no funciona, por ser error de hardware, pero para los que sean medianamente nuevos, este mini tutorial os puede ahorrar muchos dolores de cabeza. A mí me los ahorró.
http://www.htcmania.com/showthread.php?t=237713
No es magia ni un truco especial, es simplemente cambiar el módem a uno con más potencia, inyectar unos datos con el GPS Aids, borrar datos antiguos, y utilizar una aplicación de testeo que trae el propio Android que usa el módem a su máxima potencia para fijar satélites.
Comprobado que mejora. Igual os ahorráis abrir el móvil.
Saludos