Isso provavelmente acontece porque você atualizou o Ubuntu de upstart para systemctl (quando você atualizou para 16.04). E você já instalou o docker em upstart
A remoção da janela de encaixe do upstart resolverá o problema para mim:
sudo rm /etc/init.d/docker
sudo rm /etc/rc*/*docker
Depois de executar, instale novamente:
sudo apt-get install docker-engine
E verifique se o serviço de encaixe é iniciado.
sudo systemctl start docker
systemctl status docker.service