winbindd: kinit succeeded but ads_sasl_spnego_krb5_bind failed: Cannot contact any KDC for requested realm
Removing avahi-daemon fixes the issue on my machine.
I found the solutition here: https://lists.samba.org/archive/samba/2013-January/171069.html