Ah! Literally figured it out as I was reviewing this ticket. Turns out if you install docker via apt with the linode fix, it won't work. You have to install it via the curl command: curl http://get.docker.io | sh
@ysimonson do you by chance have the notes you used to get it working, I would love to add some docs for getting it up and running on linode to the docker docs. I would do it myself, but I don't have a linode account, so it makes it hard until I get off my butt and go and create one :). If you can send me the notes I can clean them up and put them in the docs.
The only thing that wasn't quite straight-forward about that was how to get to the options in the last step: "Update your Linode profile, disable "Xenify Distro", and set the kernel to "pv-grub-x86_32" or "pv-grub-x86_64" depending on your installation, then reboot the profile."
You do this by going to the linode dashboard, and clicking "edit" next to the configuration profile:
Boot the image back up and run curl http://get.docker.io | sh.