Wystarczy raz wyjść na zewnątrz i włączyć i GPS i lokalizację po sieci komórkowej. Po około minucie (ja pobawiłem się przez chwilę mapami Google) można wyłączyć lokalizację po sieci komórkowe, a używać tylko GPS i powinni już być OK.
Dwukrotnie tak zrobiłem, raz po zakupie NEXT'a i drugi po aktualizacji Androida i za każdym razem zadziałało. Co prawda dokładność wzrosła z 24 i 16 metrów do 2 metrów ale to zawsze coś.
U ciebie było 3-4 km to trochę nie teges jak na sam GPS. Może pomogłoby skasowanie pliku GPS.LOG