Cuando usaba el GPS, la manera más rápida con la que a mi me sincronizó satélites fue usando AGPS, o GPS asistido.
Es un poco "viejo" el tema, pero vamos si alguno le queréis echar un vistazo no tiene pérdida.
http://forum.xda-developers.com/show....php?t=1657108
Sincronizaba satélites en cuestión de segundos.