Tente reiniciar o serviço do gerenciador de rede.
sudo service network-manager restart
Além disso, sei que é um longo caminho e você disse o contrário, mas cd
to /etc/NetworkManager/system-connections
verifica o arquivo relevante da sua conexão Wi-Fi para ver se a senha salva do Wi-Fi é diferente daquela que você está digitando.