Не совсем понял проблемы.NM вернуть Вам необходимо?
# apt-get install network-manager
Wicd при этом можно не удалять,он появится в трее внизу слева .Конфликтов не будет.