Este problema está agora resolvido!
Depois de várias reinstalações, finalmente consegui o "sudo apt-get install bcmwl-kernel-source" para finalmente passar!
O que eu fiz de maneira diferente desta vez foi quando me pediu para instalar, eu marquei as caixas marcadas, Fazer o download e instalar quando me perguntaram sobre os dispositivos proprietários.