Hola RMNBA,
El hecho de cambiar el tipo de encriptación puede ser en ocasiones determinante para que pueda establecerse la conexión entre un router y un teléfono móvil. Ten en cuenta que al configurar este tipo de conexión entran en juego dos dispositivos y sus diferentes parámetros, y en los que algún pequeño cambio,ya sea en el router o en el teléfono, puede hacer que la conexión no sea exitosa.
En tu caso, parece que tu teléfono no era capaz de "entenderse" con el router hasta que se cambió el tipo de seguridad. Respecto a si el problema se volverá a repetir, es complicado poder pronosticarlo. De todos modos, si tu router es Movistar, te recomiendo que le eches un vistazo al foro de banda ancha fija, por si encontraras algún caso similar al tuyo. Si me indicas el modelo concreto, puedo indicarte algún hilo que puedes revisar.
Un saludo.