I had a similar plem with a Sierra Mercury air card on AT&T. I could not easily connect with WICD in XFCE. I just went to Synaptic, searched network-manager-gnome, and installed it. During installation WICD is automatically removed so you are spared the uninstall process.
Once network manager was installed and properly configured, I could connect to AT&T 3G in less than 5 seconds.
Rather than hassle with WICD, just switch to network manager. It only takes a few minutes.
Registered Linux User 483387