Meu palpite sobre o que você fez de errado é que você instalou o wicd e depois que a instalação foi concluída, você não removeu completamente o gerenciador de rede antigo executando este comando:
sudo apt-get remove --purge network-manager-gnome network-manager
Portanto, você tem dois gerenciadores de rede conflitantes diferentes e não pode se conectar à Internet.