Incrivelmente depois de tentar isso várias vezes, eu consertei usando
sudo apt-get update && apt-cache search b43
Para encontrar o pacote de firmware. Então, novamente:
sudo apt-get install firmware-b43-installer
Não faço ideia do que fiz diferente desta vez