No internet connection inside Docker containers

I cannot execute any command requiring internet connection inside any Docker container.

Works:

docker run ubuntu /bin/echo 'Hello world'

Does not work:

docker run ubuntu apt-get update

Err:1 http://archive.ubuntu.com/ubuntu xenial InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:2 http://archive.ubuntu.com/ubuntu xenial-updates InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:3 http://archive.ubuntu.com/ubuntu xenial-security InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Reading package lists...
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease  Temporary failure resolving 'archive.ubuntu.com'
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial-updates/InRelease  Temporary failure resolving 'archive.ubuntu.com'
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial-security/InRelease  Temporary failure resolving 'archive.ubuntu.com'

Similar with pip and ping.

I am on Ubuntu 16.04 and not using firewall or corporate proxy server and have tried to restart Docker. Not using docker-machine or boot2docker.

Got answer on SuperUser:

pkill docker
iptables -t nat -F
ifconfig docker0 down
brctl delbr docker0
docker -d

"It will force docker to recreate the bridge and reinit all the network rules"