Looks like a badly configured linux firewall to me.
A firewall that blocks certain types of DNS queries ?? Thats quite
a firewall that can block TXT lookups, but allows A|MX etc through ??.
I can only think of a poorly written DNS server or at the very least some
sort of semi DNS protocol aware proxy that again has been poorly written
where the author hasn't taken the full range of DNS record types into
account.
If this _is_ the case then we could really do with finding out what
is being used, and how we can work around it, because its something that
will definitely affect SPF if there are non standard servers out there
not doing what they are supposed to.