Are you starting wicd before you enter startx or after?
You are now the 4th or 5th person in the last couple of days to make this complaint. I couldnt get it to even connect to unsecured AP's. It would tell the network has encryption and needs a key.
It seems to occur when I start wicd at the initial prompt. If I wait, and start wicd in a console after I enter the KDE, it seems fine. Tell me if its the same for you.