Boas José, não sei se é este o teu caso, mas aconteceu-me o mesmo a mim, quando ainda no Ubuntu 10.10 resolvi mudar a minha "password" através do Menu que existia então.
Ou seja, não fiz através da consola! A partir daí, sempre que iniciava a sessão, ele pedia a minha "pass", a nova, eu colocava-a e, quando ligava o "wireless" aparecia essa pequena caixa de diálogo a informar que era necessária a minha "pass" pois havia uma aplicação a tentar aceder ao meu "chaveiro".
O mais intrigante é que essa segunda "pass" tinha sempre que ser a antiga, pois a nova que eu havia definido, não era aceite.
Nunca cheguei a perceber porquê!!!
Cumps.