Have you tried temporarily disabling encryption on your router to see if it can connect to open wifi? That might narrow down the cause for you. What is the output of dmesg? Try this in a terminal and see what the output is after a failed connection:
If it's an encryption issue, check the preferences-->advanced settings in Wicd and see which extrenal program it's using. It should be wext (wpa_supplicant), but I saw settings in there for like ndiswrapper and others. So if your setup is slightly different, that might be causing the issue.