Se a máquina estiver rodando 11.04 ou 11.10 você precisa desabilitar "n" executando isto em um terminal:
gksu gedit /etc/modprobe.d/options.conf
e adicionando esta linha ao arquivo:
options iwl4965 11n_disable=1
Reinicialize e tente se conectar novamente.
O Ubuntu 12.04LTS resolve esse problema (atualizarei se isso mudar).
Editar: Até agora, as versões posteriores, incluindo o Ubuntu 12.04LTS, não têm esse problema com a placa wireless Intel 4965.