There are multiple popular repositories offering docker packages for Ubuntu. The package docker.io is (most likely) from the Ubuntu repository. Another popular one is http://get.docker.io/ubuntu which offers a package lxc-docker (I am running the latter because it ships updates faster). Make sure only one package is installed. Not quite sure if removal of the packages cleans up properly. If sudo service docker restart still does not work, you may have to clean up manually in /etc/.