Então, eu descobri qual era o problema. Como minha máquina funciona em um BIOS UEFI com inicialização segura ativada, todos os drivers que podem ser carregados na pilha do driver devem ser "assinados". Eu acho que no kernel 4.4 Ubuntu, eles reforçaram essa verificação de sinais com bastante rigor. Dito isto, tudo o que fiz foi desativar a inicialização segura da minha configuração do BIOS (não digo que esta é uma solução permanente) e agora o wifi funciona como um encanto.