Toda la razón con cerdo, Para desinstalar una app de estas características tienes que tener los datos activo, pues lo que hace esto es modificar los APN y si lo desinstalas con los APN modificados, modificados te los deja.
Ve a Ajustes, redes móviles y en APN (disculpa pero ahora estoy con la ROM MIUI y no recuerdo los pasos exactos) allí si te fijjas, en tipo de APN, al final del todo, debe de poner default, si pone otra cosa, lo cambias a default y listo.