Yes, Docker works fine on Ubuntu 16.04 when you are using a distribution supplied kernel with the linux-image-extra package. On Ubuntu 16.10 it seems to work out of the box with the distribution supplied kernel (at least that was my experience on Linode a few days ago).
There’s your reason why Docker doesn’t work for you. Your kernel doesn’t support the required aufs filesystem.
Is this a custom kernel? It seems to be quite old. Ubuntu 16.04 ships with version 4.4!