Eu estava tendo problemas semelhantes. Consegui resolvê-lo indo para a página de conexão de edição da conexão em questão e inserindo a senha e o tipo de segurança (WPA no meu caso) na guia Segurança de Wi-Fi.
Você pode acessar a página de conexão de edição através do menu suspenso no ícone Wi-Fi na parte superior da área de trabalho (depois de já ter tentado se conectar); ou clicando na seta laranja no lado direito da conexão abaixo da listagem de conexões sem fio no gerenciador de rede.