There does seem to be a genuine problem with wicd and WEP, with postings on various forums. This bug post is similar to my issue: https://bugs.launchpad.net/wicd/+bug/513873. These workarounds are all viable for me (BT5R1 gnome HD install):
1. Use static IP.
2. Use network-manager. (Can be installed at same time as wicd, so you can continue to use wicd for Open and WPA).
3. Connect manually
ifconfig wlanx down
iwconfig wlanx essid ''xxxx'' key xxxxxxxx channel x
ifconfig wlanx up