Do you know which stage of the connection process (mentioned in my last post) you are at?
Have you tried methods other than using wicd to get connected?
What particular part of the connection process is causing the problem? Is there some way you could find out? What about adding new configuration settings, or removing some? What about if you changed certain settings on the wireless access point (even temporarily) to see if you can manage a connection under different circumstances. This may give you an idea where the problem lies.