Depois de se deparar com este problema, os seguintes passos colocaram o meu telefone em funcionamento (Nexus 4, r214):
Abra o aplicativo do terminal no telefone e valide-o usando a senha, se configurado
sudo stop urfkill
sudo rm /var/lib/urfkill/saved-states -rf
sudo reboot
O telefone deve voltar com a operadora reativada.