Jakub, After doing some more troubleshooting I agree that there is no problem with having multiple kdc servers.However, having more than one non-functional master_kdc is what's causing the failure. server1 and server2 are down. server3 is up this works.
kdc=server1kdc=server2kdc=server3master_kdc=server1#master_kdc=server2master_kdc=server3 this will fail: kdc=server1kdc=server2kdc=server3master_kdc=server1master_kdc=server2master_kdc=server3
I've provided the log KRB5_TRACE output and it doesn't seem like kinit is even attempting to reach server3 if it sees that the first two master_kdc are down.