Eu tenho um problema semelhante usando o Software Center e o Update Manager no Ubuntu 12.04.2. A mesma coisa, o Centro de Software não reconhece minha conexão wi-fi com o wicd. Quando clico em Instalar para pacotes, nada acontece. O Gerenciador de Atualizações verificará e fará o download das atualizações, mas ainda diz "talvez você não consiga verificar ou baixar atualizações" (ou algo nesse sentido).
Então, só por diversão, eu tentei;
sudo stop network-manager
e o mais estranho é que funcionou!
É estranho, porque eu removi o network-manager-gnome logo após instalar o wicd. Eu pensei que o gerente de rede tinha ido embora, eu acabei de remover o gui? Eu ainda preciso de um gerenciador de redes desde que eu tenho wicd?
Se não como posso realmente removê-lo sem interromper minha rede? Na primeira vez, eu o removi com o Centro de Software e ele ainda mostra como não instalado lá.
ps Obrigado pela solução acima, eu nunca teria pensado em experimentá-lo.