La geolocalización en el teléfono móvil funciona de 2 maneras:
1 - La rápida: A través las antenas de teléfono y todo el conocimiento que tenga la empresa de turno (google, apple) del posicionamiento de las wifis. Conociendo qué antenas y qué wifis tienes mas cerca se triangula tu posición. La precisión no es su fuerte pero te da la posición al instante y de forma "suficiente".
2 - La precisa: A través de los satélites GPS/Galileo/Glonass/Beidou (EEUU, Europa, Rusia, China, respectivamente) el teléfono triangula su posición a medida que va encontrando y recolectando señales de satélite. La precisión podría llegar al centímetro, pero para aplicaciones "de andar por casa" generalmente es de unos 5-10m. Tarda en conectar porque cuando se pone en marcha va recibiendo señales y hasta que no "cuadra" un mínimo de ellas no da una posición.
Se puede usar 1 o 1+2 (llamada "Ubicación precisa" en los teléfonos android)
Asegurate de tener activada la ubicación precisa, que implica al GPS, porque eso tiene que funcionar sí o sí, aún sin la SIM.
Si la ubicación precisa falla es que hay algun problema con el teléfono y cascó con el cambio de SIM como podría haber cascado en cualquier otro momento.
Para hacer las pruebas descarga GPS test o alguna app similar, que te dará toda la info de la ubicación de tu teléfono y verás si pilla o no satélites.