networking - 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.

Upd:

Update in interactive mode fails in the same fashion.

docker exec -ti angry_goodall /bin/bash
apt-get update
#fails
ping google.com
#fails with "unknown host" message
ping 8.8.8.8
# shows PING 8.8.8.8 (8.8.8.8): 56 data bytes
# and than hangs indefinetly

sudo apt-get update runs successfully on host, i.e. on my computer outside docker.

Upd Docker version 1.12.1, build 23cf638

Answer

As suggested by creack on GitHub issue #866 for Docker:

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"