Извините, сразу почему то не разобрался.
Я оставлю тут решение и объяснение, если для кого то оно так же не очевидно.
Правильно будет так:
iptables -A INPUT -p udp --dport 53 -j ACCEPT
iptables -A OUTPUT -p udp --sport 53 --dport 1024:65535 -j ACCEPT
Потому что днс запрос от клиента к серверу уходит на 53 порт, ответ от сервера к клиенту с 53 порта, но возвращается к клиенту на один из портов в диапазоне 1024:65535.
