Supondo que você esteja executando uma versão mais recente do Ubuntu, execute os seguintes comandos para atualizar seu kernel:
sudo apt-get update
sudo apt-get dist-upgrade
Em seguida, reinicie para que as alterações entrem em vigor.
Supondo que você já esteja executando o kernel mais recente, execute o seguinte comando para aumentar o limite de tentativas que pode ser um problema e causará os problemas que você está enfrentando se estiver definido muito baixo (o padrão é 7):
sudo iwconfig wlan0 retry 12
Se a alteração das configurações do iwconfig funcionar para você, você terá que fazer isso sempre que reiniciar.
Se você estiver executando o Ubuntu 12.04, por favor me avise e eu incluirei instruções sobre como construir o driver a partir do código fonte disponível no site realtek (instalará somente no 12.04 e não irá compilar em um kernel mais novo).