I have been having a similar problem. Unfortunately, none of the proposed solutions given above have worked for me.

I have a Zoom DSL-modem/wireless-router, serving two computers in my home. The desktop box is normally connected via an Ethernet cable. The laptop had, for several months, been connected via wifi.

The first six months I owned the laptop, I ran it with the Windows XP Pro OS. Last July, I re-formatted to run Ubuntu Linux (v. 8.04). For the first couple months on Ubuntu, I had no problem connecting to my wireless network or to other wireless networks.

Suddenly, sometime in September, I was no longer able to connect to my wireless network. The network manager will see the signal (and recognize the encryption type, the correct broadcast channel, etc.) but it doesn't connect.

There are other, unsecured wireless networks in my neighborhood, and I've been able to connect to them. I checked the broadcast channels on all of them, and none are set to use the same channel as my system.

I can put my laptop on my computer desk, plug in an Ethernet cable, and be connected to my LAN and to the Internet

I tried connecting wireless with from my desktop box (running Windows XP Pro): shut down power, unplugged the Ethernet cable, installed a wireless card, and powered back up. Same result as the laptop -- my wireless network is visible, but it won't connect.

I've tried shutting everything down -- both computers and the modem-router, then re-booting the router first, then the computers (after the router shows full connection to the Internet). Still no joy.

I've uninstalled the Network Manager that came with Ubuntu and installed wicd instead. That shows me a little more detail, but I still cannot get a connection with my wireless system. The wicd window shows a message "Configuring WPA Authentication code" then "Validating Authentication" but that step appears to fail. At least, after showing that message for a minute or so, the process stops and I'm still not connected.

All of this leads me to suspect the trouble is in my router. Is it possible for the router to connect via Ethernet cable and to broadcast its SSID, channel selection, encryption type, etc., but somehow be unable to validate the WPA key? (I know I've entered the correct key -- I've gone through this exercise at least twenty times, and on a few occasions I've even logged onto my router, using the Ethernet cable, and used copy-and-paste to pick up the key from the router and apply it to the network manager.)