Eu tive um problema semelhante com o elementar 0.4 Loki (que usa o Ubuntu 16.04 como base). Não encontrei uma solução, mas pelo menos uma solução alternativa:
É suficiente abrir as configurações de rede e editar a conexão. Se você tentou se conectar uma vez que a rede wifi aparecerá como uma rede usada recentemente. Se você, em seguida, editar a rede wifi, você pode digitar a senha na guia "segurança", e voilà ele funciona.
Portanto, parece que o problema é que a senha não é salva nas configurações após a primeira tentativa de conexão.