We have been seeing this intermittently in our different kubernetes clusters, kube-dns is not resolving some hosts names and it is causing failures with some batch jobs or containers that are dependent on others to start.
We know that the networking is working because we are able to reach services or containers with IPs. So I had to stop blaming flannel.
Our Linux architect noticed that br_netfilter module was loaded but not the xt_physdev one.
On each node he fixed it with these commands (first and last ones to verify the loaded modules and second to load the missing module):
[root@server ~]# lsmod | grep br_ br_netfilter 22209 0 bridge 136173 1 br_netfilter [root@server ~]# modprobe xt_physdev [root@server ~]# lsmod | grep br_ br_netfilter 22209 1 xt_physdev bridge 136173 1 br_netfilter
Everything started to work perfectly after that little fix.