Não procure os drivers na Internet, /sbin/vboxconfig
os cria.
O problema era que os drivers antigos ainda estavam presentes e preferidos.
Então eu removi os drivers antigos e executei /sbin/vboxconfig
novamente, dessa vez funcionou.
sudo mv /lib/modules/3.16.0-4-amd64/updates/dkms/vbox* /tmp
(Movendo para / tmp em vez de rm apenas no caso)
O diretório pode variar, eu encontrei no primeiro comando da minha pergunta com o lsmod e modinfo.
Então sudo /sbin/vboxconfig
e deve funcionar
Os novos drivers estão em /lib/modules/3.16.0-4-amd64/misc/
(Não há necessidade de reiniciar.)