Since no one replied yet, I'll try a few stabs at debugging. DNS by default uses UDP for most things, so your DNS servers might simply be rejecting TCP requests. That said, why are they even getting to the server and being refused there if the firewall is dropping the packets? You might try starting with a very simple ruleset and see if you can pinpoint where the problem occurs, especially if this is a personal computer and not a large installation. For example, just allow DNS in a stateless fashion, then introduce stateful rules. Keep track of packet counters in iptables as you test to see which rules fire. Hopefully this helps, though I'm being rather vague because I don't know too many details and am rather new myself.
