Network Manager is an excellent wireless/wired/VPN/Dial-up network manager, but it doesn’t always work well.
A worthy replacement is Wicd.
To install it, you can follow the instructions on the Ubuntu Wiki, but on Lucid Lynx, when it tries to uninstall the Network Manager packages (“network-manager” and “network-manager-gnome”), it fails.
You might say “Who cares? I’ll leave them there and start Wicd!”.
Why? In my case, they conflicted with each other and Wicd couldn’t connect.
So, after installing Wicd (with a simple “sudo apt-get install wicd”), I removed the Network Manager packages with a “clean sweep”:
sudo apt-get autoremove network-manager
In my case, Wicd connected instantly :D.
Bye!
! :) !