Running BT5R3 amd64. Ran update/upgrade...wicd wouldn't work so I looked and looked and looked, but the solutions didn't seem to work in my case. I reinstalled and ran into more wicd issues such as it disappearing entirely. So, here is what worked for me. I hope maybe it will help someone down the road.

I had to install several packages. This was a challenge since I was trying to connect via usb tether as it was my only choice at the time and location. What I did was download the packages from Windows 7 since that is my primary OS. I then rebooted in BT and moved the files over. I think this took about 10 reboots in the end, but I got there. Here are the packages and order I installed them:

python-wicd_1.7.0+ds1-6_all.deb
dhcpcd-dbus_0.5.2-2_amd64.deb #this ended up not being needed
dhcpcd5_5.2.12-1_amd64.deb #this might not be needed. I have not removed it, but after installing it I still had no working wicd.
dhcpcd_3.2.3-9ubuntu0.1_amd64.deb #i think this was what I really needed as opposed to the previous 2 ^^^
wicd-kde_0.2.1-5_amd64.deb #after this and reboot I now had working wicd and also an icon in the systray which was not my goal, but a nice bonus

After this I went into wicd and connected via usb0. I got an IP address, but my internet connection still wouldn't work. After glancing at more topics I did 2 things:

in /etc/network/interfaces I added "auto usb0 iface usb0 inet dhcp" #I don't think I needed this

in /etc/resolv.conf I added a line "nameserver 192.168.x.x" #the IP I used was the gateway listed after running the "route" command.
#after this I tried again and had a successful connection.

I hope someone out there finds this helpful!