Some time ago I found out that you have to install some not-so-well-documented updates (which are not delivered automatically by Windows Update) to use WPA2 to encrypt the traffic of your wireless network (and it is advised to use WPA2, since all the prior standards have known weaknesses).
However I was unpleasantly surprised that support for WPA2 on the Linux side (at least from a GUI standpoint) is also lacking. When using Ubuntu 8.10 + network-manager, I was unable to connect to a WPA2 encrypted network (this is not specific to Ubuntu, I had the same experience with Fedora 9 for example). When I entered the (correct) password, it kept saying that the password was incorrect and showing the hashed password.
I found some command-line level workarounds, but finally I settled on using wicd: it is an alternative to network manager, has much more options and has ready-made packages (beginning with Jaunty, it will also be present in the universe repository). It worked flawlessly for me as a network-manager replacement and using it I could connect to the encrypted network.
Do I expect it to replace network-manger? Not really. It is very much a power-user tool. While it offers much more options than the vanilla network-manager, however it can easily be overwhelming for a beginner user. So there you have it folks: if you are having problems with the network, or simply want to have a more powerful tool for managing it, try out wicd.
PS. An added benefit (for me) is that it doesn’t show the “you are not connected to the network X” popups, which annoy me and are reminiscent of Windows XP.
Picture taken from Darwin Bell's photostream with permission.