Connect to network says "Connection failed" but it actually isn't

On most occasions, when I try to connect to a new wi-fi network, after I enter the password and click "Connect" the connection dialog says "Connection failed" after a little pause, but in fact the connection is established, the menubar widget displays the network and everything works normally.

Except the network is never saved to the list of known networks, so every time I have to enter the password again.

What may be the issue here?

OS X 10.7.3, Macbook Air 13" late-2011

I had the same problem. I could connect although it said "connection failed." I observed that my network was also not in the preferred networks list. I resolved the problem in two steps. I manually entered my network's name and my networks password to keychain list. After that, in the system preferences advanced window, I manually added my network to the list of preferred networks by clicking on add button (+) and dragged it to the first line of the list. I hope this helps.