This issue is similar to “Ubuntu updates intefere with docker and aufs”.
If you are using Ubuntu 14.04 LTS, regardless of whether you run on Linode, or any OpenStack powered providers, you can take a look at my answer I posted there
First post I made in this thread made me write a long answer that was going wider than answering the question of that thread. I decided to move it to a blog post instead.