Estou com problema semelhante. Quando entro, às vezes a rede "pega" de primeira. Outras vezes, o applet fica piscando e pede a senha da rede. Após 1 ou 2 tentativas, ele sempre acaba conectando.
O curioso é que, quando comecei a usar o Ubuntu, acho que lá pelo 8.10, dava esse problema. A partir de 9.04, não aconteceu mais e ele conectava direto. Antes desta instalação do 11.10, eu estava com a 10.04LTS e nunca aconteceu isso. Agora, com a 11.10, voltou a acontecer.
Um abraço.