Authentication Services needs DNS functioning properly and was just reacting to DNS queries not providing us answer. We did the ping to the DNS server with the udp / 1469 size and that worked, but at 1600 it timed out. From traceroute, we saw the DNS server was 16 hops away, and from mtr say it was failing near the end of the connection.