Problema de.conexión

Hola. Tengo un problema con mi celular Samsung Gala s5, lo uso con una simcard de Claro, dentro de la ciudad no tengo ningún problema para hacer o recibir llamadas pero en cuanto salgo de la ciudad se desconecta de la red. El celular marca la señal de Red pero no se puede conectar. Lo he probado con otra sim y sucede lo mismo. La sim de Claro la colocó en otro celular que tengo y se conecta perfectamente por todo el camino. A mi Samsung S5 le colocó una simcard de otra compañía y sigue con el mismo problema, se desconecta en cuanto salgo de la ciudad. Leyendo encontré que probablemente era cuestión de la rom por lo que he probado como 4 roms diferentes y con todos hace lo mismo.
Ayuda por favor, si tengo una emergencia en carretera no puedo usar el teléfono porque no se conecta a la red.
Nota: Ya probé cambiando todos los modos de Red.