Eu instalo meu Docker assim:
1) Verifique a versão do Linux: uname -a
- > sua versão do Kernel precisa ser maior que 3.8
2) Faça uma atualização do sistema: sudo apt-get update
3) Adicionando a chave GPG:
sudo apt-key adv \ --keyserver hkp://ha.pool.sks-keyservers.net:80 \ --recv-keys 58118E89F3A912897C070ADBF76221572C5609D
4) Verifique a conexão do servidor:
sudo apt-add-repository 'deb https://apt.dockerproject.org/repo ubuntu-xenial main'
5) Baixando a imagem do Linux:
sudo apt install linux-image-generic linux-image-extra-virtual
6) Reiniciando o sistema: sudo reboot
7) Download da janela de encaixe:
sudo apt install docker-engine
8) E, finalmente, para testar, baixe alguma imagem:
sudo docker run hello-world
Funciona bem para mim, a mensagem foi porque durante a instalação você sente falta de instalar algumas coisas importantes