A solução fácil para o seu problema seria instalar o NetworkManager de volta.
Mas como você o instala de volta se você não tem acesso à Internet?
É possível conectar-se manualmente à Internet usando um cabo Ethernet (tecnicamente é muito mais fácil do que uma conexão sem fio).
Portanto,
- conecte o computador com um cabo Ethernet ao roteador,
- abre uma janela de terminal ('gnome-terminal') e executa
dhclient eth0
(você deve ter acesso à Internet agora) - e finalmente inicie o Centro de Software e instale
network-manager-gnome
.