Acabei de corrigir o problema, descobri que os fontes do kernel não foram instalados, o que impediu a compilação adequada do driver. Então, eu instalei o kernel source para o kernel atual do Synaptic e então emiti os seguintes comandos e meu WiFi foi instantaneamente restaurado (como 3 ou 5 segundos).
Para instalar os cabeçalhos e a origem do kernel:
sudo apt-get install linux linux-headers-generic kernel-package
sudo apt-get purge b43-fwcutter firmware-b43-installer firmware-b43-lpphy-installer firmware-b43legacy-installer bcmwl*
sudo apt-get install b43-fwcutter firmware-b43-lpphy-installer bcmwl*
Em seguida, reinicie.
Isso se aplica somente ao BCM4312 (Meu laptop é Lenovo g450)
Para outros podem ver esta postagem do blog , isso pode ser útil para você.