Este é realmente um problema de duração mínima da senha, como você afirmou. O engraçado é que quando a conexão é feita automaticamente, o Ubuntu não parece reclamar. É somente quando uma conexão é tentada através da GUI que o problema ocorre.
Você pode tentar reiniciar a rede ...
Ou ...
sudo /etc/init.d/networking restart
ou ...
sudo service networking restart
Ou ... você pode tentar usar um script para obter uma conexão ...
#! /bin/bash
ifconfig wlan0
iwconfig wlan0 essid [NETWORK_ID] [key WIRELESS_KEY]
dhclient wlan0
Isto assume que sua interface é chamada wlan0
.