Está instalando e configurando wicd fora de questão? Eu usei network-manager em vários laptops com vários cartões wifi e dongles, e às vezes network-manager funciona bem ... mas quando falha, não dá muita informação sobre o que pode estar errado, às vezes seus erros omitem alguma parte necessária dos dados de depuração, outras vezes as mensagens são vagas.
Como um " Plano B ", wicd não é perfeito, mas para alguns problemas sua GUI é mais fácil de configurar, seu seletor de rede wifi mostra mais informações, e muitas vezes apenas funciona quando network-manager não.
Bônus: Em sistemas baseados em Debian , os dois gerenciadores de wi-fi podem coexistir. A desinstalação não é necessária.