I was getting this error message because docker was refusing to start: Cannot connect to the Docker daemon. Is 'docker -d' running on this host?
This issue was occurring because my kernel was refusing to upgrade, because I was on a VPS. (you need to get your VPS provider to upgrade it for you)
Run uname -r, if it returns something like this: "2.6.32-042stab084.20" That's probably the reason why docker isn't starting. Your kernel isn't compatible.
If you're not on a VPS and can upgrade your kernel, try instructions on this page: http://docs.docker.io.s3-website-us-west-2.amazonaws.com/installation/ubuntulinux/