This just happened on my Linode (+ AUFS support) too. I had updated with apt-get dist-upgrade -y
and rebooted.
Running docker daemon
showed
[graphdriver] prior storage driver “aufs” failed: driver not supported
What fixed it was $ sudo apt-get install linux-image-extra-`uname -r` && sudo modprobe aufs
as suggested by @danwad .