Comecei a experimentar problemas semelhantes após atualizar o Ubuntu para o 11.10 em um netbook Acer 532h.
Como um dos outros comentadores, tenho tentado corrigir esse problema usando o gerenciador de rede 'wicd' em vez do padrão 'network-manager' e 'network-manager-gnome'. Depois de tentar isso sem nenhum resultado imediato, pesquisei ainda mais essa questão e descobri que esses problemas parecem afetar muitos laptops diferentes e não os da marca Acer especificamente.
Se, como eu, você tiver o erro "Senha inválida" específica ao usar a criptografia wicd e WPA, uma das soluções sugeridas aqui: link
pode aproximá-lo de uma solução.
Observe que eu ainda não consegui fazer meu Wi-Fi funcionar de forma estável no Ubuntu, mas estou convencido de que meu problema (e possivelmente o seu!) está relacionado a esse problema.
Minha rede sem fio está funcionando bem se eu iniciar o Windows 7 no netbook e outros dispositivos sem fio estiverem se conectando sem problemas.