Por favor, abra um terminal e faça:
gksudo gedit /etc/network/interfaces
Altere o arquivo para:
auto lo
iface lo inet loopback
auto eth0
iface eth0 inet dhcp
Revise, salve e feche o gedit. Agora faça:
sudo ifdown eth0 && sudo ifup -v eth0
Agora, sua ethernet deve estar conectada para que você possa reinstalar o NM ou o Wicd. Depois de fazer isso, repita o processo, mas remova as linhas eth0 se você selecionar NM. Eu acredito que as linhas eth0 podem permanecer para Wicd.