Ответ @Telorand был очень полезен, но тогда эта ошибка была в syslog:
Firmware file "b43/ucode5.fw" not found
Итак, я нашел эту страницу, которая рекомендовала использовать firmware-b43-installer вместо firmware-b43-lpphy-installer. [ ! d1]
С Dell Latitude D630 и той же проблемой это помогло:
sudo apt-get update
sudo apt-get remove --purge bcmwl-kernel-source
sudo apt-get install firmware-b43-installer b43-fwcutter