I have a very similar problem with the WLAN in my university. It has a lot of access points to cover the whole area. So I usually can reach several access points with the same SSIDs working on different channels.
Normally I would like to connect to the access point with the highest connectivity, but when I click connect on the item in wicd's list, it seems to pick one of the access points at random. In order to get a good connection (to the right AP) I have to reconnect a few times.
This is on gentoo with a 2.6.32-tuxonice kernel and wicd 1.7.0.