I was getting the same behavior in WEP, WPA... etc. Seldom i can got an ip address from DCHP.
I stopped using wicd, i get associated with the AP using wpa_supplicant and run dhclient, dhclient3, udhcpc and almost every dhcp client and the problems remains the same. "Unable to get an IP add...".
The problem was no wicd, associations occurs well using WEP, WAP or OPEN. I set manually my IP address and default route and my DNS at resolv.conf, using the following commands and it works.
ip address add <ip_address>/<netmask> dev <wireless_iface>
ip route add default via <gateway_ip_address> dev <wireless_iface>
echo <dns_server_address> > /etc/resolv.conf
Next i decided to browse the content of the file /etc/dhcp3/dhclient.conf. The following line kept my attention (the line states this, literally, including angle brackets)
send host-name "<hostname>"
...and it was uncommented!!
I replaced the value <hostname> with my current hostname like this:
send host-name "linuxbox"
Launch wicd and everything works as it should.
I hope this would work for others, and yes... English is not my mother language.
best regards to the community!!!