DNS was precisely the area where we got bit by it.

We were using a Non-AWS DNS resolver (aka Google) and we would often get dns resolution errors despite our NAT not being remotely taxed by the traffic.