A solução estava seguindo este tutorial para instalar o kernel 4.4.0 no Mint. E reinstalar o docker (várias vezes, desde que eu tinha uma configuração anterior corrompida), porque eu tinha instalado usando um one-liner e um script, e não segui as instruções de instalação no site oficial do Docker, acredito.
Então, agora eu poderia executá-lo com:
$ uname -r
4.4.0-040400-generic
$ docker version
Client:
Version: 1.12.3
API version: 1.24
Go version: go1.6.3
Git commit: 6b644ec
Built: Wed Oct 26 21:44:32 2016
OS/Arch: linux/amd64
Server:
Version: 1.12.3
API version: 1.24
Go version: go1.6.3
Git commit: 6b644ec
Built: Wed Oct 26 21:44:32 2016
OS/Arch: linux/amd64
Não é exatamente uma solução para o problema, pois não consegui descobrir por que ele não estava funcionando, mas está funcionando agora (testado com as imagens do ubuntu e do sonar, ambas funcionaram bem).