El acceso a la ubicación es utilizado por el GPS, como bien dices, pero también por otras aplicaciones (Google) a través de datos y/o Wifi. Comprueba que esta última está desmarcada y que Google Maps, etc... no tienen acceso a tu ubicación.
Te adjunto capturas de mi cacharro, una de ellas es anterior al cambio de Rom, observarás que en Modo avión seguía descargando batería. Pero la calidad de la señal de radio es mucho mayor que la de tu teléfono (mucho "verde").
UY, no sé poner la imagen!!!
Podrías probar a instalar la versión libre alemana a ver si mejora la recepción.Antes comprueba con otro móvil que tenga el mismo operador la cobertura (señal de radio) -> Ajustes-> Información del teléfono-> Estado -> Intensidad de la señal. Yo ponía mi viejo HTC Desire X junto al S4 Mini y tenía más señal en el HTC hasta que cambié la ROM al Mini.
Si lo de la Rom alemana no funciona ya te aconsejo que le metas el Cyanogenmod (recuerda que te quedas sin garantía).
