I've had the same problem with a VPS provider, couldn't install or run docker. It turns out, docker requires at least a 3.x kernel, while some providers run on 2.x and won't allow a kernel update to enable docker's virtualization. Of course, they had other plans with full virtualization, but for $$$$ more. Screw that, I had to find another place.