I had the same issue on kubernetes v1.6 and it was not a firewall issue in my case.

The problem was that I have configured the DNS manually on the /etc/docker/daemon.json, and these parameters are not used by kube-dns. Instead it is needed to create a configmap for kubedns (pull request here and documentation here), as follows:

Solution

Create a yaml for the configmap, for example kubedns-configmap.yml

apiVersion: v1
kind: ConfigMap
metadata:
  name: kube-dns
  namespace: kube-system
data:
  upstreamNameservers: |
    ["<own-dns-ip>"]

And simply, apply it on kubernetes with

kubectl apply -f kubedns-configmap.yml

Test 1

On your kubernetes host node:

dig @10.96.0.10 google.com

Test 2

To test it I use a busybox image with the following resource configuration (busybox.yml):

apiVersion: v1
kind: Pod
metadata:
    name: busybox
spec:
    containers:
    # for arm
    #- image: hypriot/armhf-busybox
    - image: busybox
      command:
          - sleep
          - "3600"
      imagePullPolicy: IfNotPresent
      name: busybox
    restartPolicy: Always

Apply the resource with

kubectl apply -f busybox.yml

And test it with the following:

kubectl exec -it busybox -- ping google.com

The issue turned out to be that a node-level firewall was interfering with the cluster networking. So there was no issue with the DNS setup.