moby: Cannot connect to the Docker daemon. Is the docker daemon running on this host?

Description

I cannot use Docker on my brand-new AWS instance, where it was installed out-of-the-box.

Steps to reproduce the issue:

1. Trying to start docker via sudo service docker start. This steps returns OK.
2. running docker info returns Cannot connect to the Docker daemon. Is the docker daemon running on this host?
3. running any other Docker command returns the same

Describe the results you received: Cannot connect to the Docker daemon. Is the docker daemon running on this host?

Describe the results you expected: Successful execution of commands

Additional information you deem important (e.g. issue happens only occasionally): Full log from /var/log/docker

Output of docker version: Client: Version: 1.12.6 API version: 1.24 Go version: go1.6.3 Git commit: 7392c3b/1.12.6 Built: Fri Jan 6 22:16:21 2017 OS/Arch: linux/amd64 Cannot connect to the Docker daemon. Is the docker daemon running on this host

Output of docker info:

Cannot connect to the Docker daemon. Is the docker daemon running on this host?

Additional environment details (AWS, VirtualBox, physical, etc.): AWS t2.micro AMI Linux 2016.09d