A primeira coisa que eu adiciono à uma nova instalação de Gnu/Linux em um laptop, é o programa Network Manager (sudo aptitude install network-manager-gnome). Este programa foi a melhor invenção no mundo Gnu/Linux desde a invenção do pão fatiado! Com ele você não tem de memorizar nomes e senhas para pontos de acesso de redes sem fio. Mas uma coisa que eu notei foi que se você instalar o programa depois de já ter acessado um ponto de acesso, ele simplesmente não funciona!

A solução é bem simples, mas infelizmente não intuitiva: edite o arquivo de interfaces de rede, e remova qualquer linha referente ao seu dispositivo de rede sem fio.

sudo vim /etc/network/interfaces

Procure pelas linhas já configuradas do dispositivo e as remova:

wireless-essid Mordor wireless-key theonetobindthemall

Não se esqueça de salvar o arquivo. Agora, desabilite o Network Manager e o habilite novamente em seguida, para que o arquivo possa ser recarregado, e pronto.