Isso soa como um problema com o chaveiro do Gnome. Sugiro o backup do diretório ~/.gnome2/keyrings e tente removê-lo para ver se isso ajuda. É claro que, quando você redigitar suas senhas para o Evolution ou uma rede sem fio, ele solicitará que você crie uma senha para o chaveiro recém-criado (imagem mostrada abaixo). Certifique-se de que a senha seja igual à sua senha de login.
Além disso, se você se conectar a uma rede sem fio e fizer login automaticamente, selecione "Disponível para todos os usuários" nas configurações sem fio.