Eu também tive um problema semelhante a partir do dia 10 (apesar de admitir que não tenho um cartão da Broadcom), e parece que o Network Manager foi o culpado. Eu não encontrei uma solução simples, mas consegui arrancar a partir de um live CD, montar o disco rígido, apt-get remover network-manager e apt-get install wicd. O Wicd parece ter alguns problemas durante a inicialização, mas se eu começar manualmente, ele encontra e se conecta ao meu wireless muito bem.
Aqui estão as instruções passo-a-passo, para qualquer pessoa com problemas semelhantes que também esteja tendo problemas com sua ethernet (que também foi um problema no meu computador):
Reinicie e carregue o CD ao vivo. Vá para "Try Ubuntu"
Abra um terminal e digite:
sudo su -
mount /dev/sda1 /mnt
mount --bind /proc /mnt/proc
mount --bind /dev /mnt/dev
mount --bind /sys /mnt/sys
chroot /mnt
apt-get remove network-manager
apt-get install wicd
A partir daqui, você pode fazer qualquer outro pacote (des) instalações. Então,
umount /mnt{/proc,/dev,/sys,}
umount /mnt
E reinicie.
Para referência, estou usando uma interface sem fio Intel. A reinicialização de kernels diferentes não resolveu o problema, mas a inicialização do Live CD foi boa, assim como o trabalho do Debian ou do Gentoo.