Eu tive o mesmo erro hoje depois de atualizar o docker-ce para a versão 18.09.0 no Debian 9. Eu não posso te dar uma solução para essa versão, mas voltar para a versão 18.06.1 fez com que ela começasse novamente. Para o Ubuntu, isso deve ser:
sudo apt-get install docker-ce=18.06.1~ce~3-0~ubuntu
A versão 18.09.0 já funcionou para você? Minha instalação caiu logo após a atualização.
Editar: Na verdade, existe um relatório no GitHub relacionado a esse problema. link
Parece que o novo containerd
está tentando carregar o módulo de sobreposição mesmo quando já está carregado. O módulo de sobreposição é carregado no meu sistema, mas não consigo encontrar o arquivo em /lib/modules/