Docker 1.9 provides new, improved, functionality for networking.
If you are still on 1.6 (perhaps because your favourite Linux distro hasn't yet included 1.9), then you may find that you lose network access from your Docker containers after a firewall change on the host system. It seems that the docker0 virtual network device sometimes gets mangled.
If you have the ability to ping between containers, but they can't access the Internet despite routing rules seeming to be correct, we suggest that you try reinitialising docker0 by the following means:
pkill docker iptables -t nat -F ifconfig docker0 down brctl delbr docker0 docker -d
Note that this will clear all rules from the nat table, so make sure you put others back if you have nat rules other than those for docker!