Estou usando um dongle USB da Belkin para conectar-me à minha rede Wi-Fi com uma chave wpa2. Na maioria das vezes, o Ubuntu não é capaz de se conectar à rede automaticamente e continua pedindo a chave, mesmo que a chave correta já tenha sido digitada.
Ele se conecta depois de reiniciar a rede várias vezes.
Estou no dia 11.04 com as atualizações mais recentes.
Tente usar o wicd em vez do gerenciador de rede nativo. Eu tive problemas semelhantes, principalmente relacionados a desconexões inesperadas do wifi - depois de atualizar para o 11.04. Eu nunca tive esse problema em versões anteriores do Ubuntu para ser honesto.
Uma vez eu tive que usar um Acer Aspire TimelineX que tinha uma placa wireless sem suporte. Eu baixei wicd via wired e funcionou perfeitamente, embora não apareça no seu painel.