NetworkManager should support b43 and b43-legacy, what happens if you try to make it work with a WEP key using these commands
Code:
su
iwconfig wlan0 essid [insert wlan network name here] key [insert WEP key here]
ifconfig wlan0 up
dhcpcd wlan0
Do you get internet?
If you do it's surely a problem with NM