É um bug conhecido, já relatado link
Desde a atualização para o 16.04 LTS, não consigo me conectar manualmente a uma rede salva.
Eu posso conectar se a rede não estiver oculta após uma nova verificação - basta selecionar a rede no menu ou esperar que ela se conecte automaticamente. Eu também posso conectar se eu digitar os detalhes manualmente. No entanto, se eu selecionar uma rede salva, o botão Conectar na caixa de diálogo ficará esmaecido.
Eu tentei salvar uma nova versão da rede, mas tenho o mesmo problema. Eu também tentei armazenar a senha apenas para o usuário atual e para todos os usuários, mas ambos têm o mesmo problema.
É um bug conhecido, já relatado link
Como solução alternativa, se a rede não estiver oculta, você poderá forçar uma varredura executando
sudo iwlist wlan0 scan
em que wlan0 é o nome da sua interface sem fio.
Para (possivelmente) adicionar mais a este problema, eu acabei de fazer uma instalação limpa em um IBM Thinkpad do Ubuntu 16.04LTS, e tudo correu bem até a instalação terminar. O roteador é um SSID oculto e não pôde se conectar. Tendo o controle do roteador, tornei o SSID visível e, após a reinicialização do Thinkpad, consegui me conectar. Durante a sessão, redefini o roteador para SSID oculto, o Thinkpad conseguiu manter a conexão com o SSID até ser reiniciado. Na reinicialização, ele não pôde mais se conectar ao SSID oculto. É claramente uma questão de não ser capaz de negociar um SSID oculto. Dos vários problemas relatados em vários envios de bugs, é óbvio que há mais de um problema de conectividade com bugs ainda no 16.04LTS.