Então, finalmente consertamos. Baseado na resposta em O Samba não inicia após atualizar para 16.04 , eu tive que limpar todos os pacotes de samba primeiro.
Então, eu corri:
aptitude purge samba libnss-winbind libpam-winbind samba-dbg system-config-samaba winbind smbclient samba-testsuite samba-common-bin samba-dev samba-doc samba-dsdb-modules samba-vfs-modules
(Eu não sei onde eu peguei alguns desses, acho que eu estava seguindo a solução de alguém que disse para instalar o samba *)
Então eu corri
aptitude install samba libnss-winbind:amd64 libpam-winbind:amd64 winbind -f
(certifique-se de que a arquitetura correta do sistema seja usada - o meu é um AMD64).
service smbd start
service nmbd start
então funcionou!