I had some unresolved errors after removing /var/lib/docker/aufs, which a couple extra steps cleared up.
To add to @benwalther answer, since I lack the reputation to comment:
# Cleaning up through docker avoids these errors
# ERROR: Service 'master' failed to build:
# open /var/lib/docker/aufs/layers/<container_id>: no such file or directory
# ERROR: Service 'master' failed to build: failed to register layer:
# open /var/lib/docker/aufs/layers/<container_id>: no such file or directory
docker rm -f $(docker ps -a -q)
docker rmi -f $(docker images -a -q)
# As per @BenWalther's answer above
sudo service docker stop
sudo rm -rf /var/lib/docker/aufs
# Removing the linkgraph.db fixed this error:
# Conflict. The name "/jenkins_data_1" is already in use by container <container_id>.
# You have to remove (or rename) that container to be able to reuse that name.
sudo rm -f /var/lib/docker/linkgraph.db
sudo service docker start