Intermittent failures in kinit on IPA server on RHEL6

Issue

kinit as any IPA user fails with the error:

kinit: Cannot contact any KDC for realm 'REALM'

Looking at the strace:

# egrep 'socket|connect|sendto' strace.out
28817 00:47:05 socket(PF_NETLINK, SOCK_RAW, 0) = 3 <0.004491>
28817 00:47:05 sendto(3, "\24\0\0\0\26\0\1\3\211\33\355T\0\0\0\0\0\0\0\0", 20, 0, {sa_family=AF_NETLINK, pid=0, groups=00000000}, 12) = 20 <0.000019>
28817 00:47:05 socket(PF_FILE, SOCK_STREAM|SOCK_CLOEXEC|SOCK_NONBLOCK, 0) = 3 <0.004736>
28817 00:47:05 connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory) <0.000822>
28817 00:47:05 socket(PF_FILE, SOCK_STREAM|SOCK_CLOEXEC|SOCK_NONBLOCK, 0) = 3 <0.000012>
28817 00:47:05 connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory) <0.000014>
28817 00:47:05 socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 3 <0.003785>
28817 00:47:05 connect(3, {sa_family=AF_INET, sin_port=htons(88), sin_addr=inet_addr("IP.ADDRESS")}, 16) = 0 <0.000017>
28817 00:47:05 sendto(3, "j\201\2550\201\252\241\3\2\1\5\242\3\2\1\n\243\0160\f0\n\241\4\2\2\0\225\242\2\4\0\244\201\2150\201\212\240\7\3\5\ \0\0\20\241\0220\20\240\3\2\1\1\241\t0\7\33\5admin\242\f\33\nDOMAIN\243\0370\35\240\3\2\1\2\241\0260\24\33\6krbtgt\33\nDOMAIN\244\21\30\01720150225004705Z\245\21\30\01720150226004705Z\247\6\2\4p\267\254U\250\0160\f\2\1\22\2\1\21\2\1\20\2\1\27", 176, 0, NULL, 0) = 176 <0.000027>
28817 00:47:06 socket(PF_INET, SOCK_STREAM, IPPROTO_IP) = 4 <0.006291>
28817 00:47:06 connect(4, {sa_family=AF_INET, sin_port=htons(88), sin_addr=inet_addr("IP.ADDRESS")}, 16) = -1 EINPROGRESS (Operation now in progress) <0.000074>
28817 00:47:09 sendto(3, "j\201\2550\201\252\241\3\2\1\5\242\3\2\1\n\243\0160\f0\n\241\4\2\2\0\225\242\2\4\0\244\201\2150\201\212\240\7\3\5\  \0\0\20\241\0220\20\240\3\2\1\1\241\t0\7\33\5admin\242\f\33\nDOMAIN\243\0370\35\240\3\2\1\2\241\0260\24\33\6krbtgt\33\nDOMAIN\244\21\30\01720150225004705Z\245\21\30\01720150226004705Z\247\6\2\4p\267\254U\250\0160\f\2\1\22\2\1\21\2\1\20\2\1\27", 176, 0, NULL, 0) = 176 <0.000041>
28817 00:47:14 sendto(3, "j\201\2550\201\252\241\3\2\1\5\242\3\2\1\n\243\0160\f0\n\241\4\2\2\0\225\242\2\4\0\244\201\2150\201\212\240\7\3\5\0@   \0\0\20\241\0220\20\240\3\2\1\1\241\t0\7\33\5admin\242\f\33\nDOMAIN\243\0370\35\240\3\2\1\2\241\0260\24\33\6krbtgt\33\nDOMAIN\244\21\30\01720150225004705Z\245\21\30\01720150226004705Z\247\6\2\4p\267\254U\250\0160\f\2\1\22\2\1\21\2\1\20\2\1\27", 176, 0, NULL, 0) = 176 <0.000029>