DNS or Firewall?

I have a rather unique problem with my setup. I currently have one Active Directory integrated DNS server and one Linux DNS Server running on our LAN. We recently upgraded our Cisco firewall with WS-SVC-FWM1 and suddenly we started seeing this message:

[code:1]Jun 13 2008 14:58:11: %FWSM-2-106007: Deny inbound UDP from 172.xx.xxx.xxx/53 to host1/33327 due to DNS Response[/code:1]

We then put a sniffer on the network to capture all DNS traffic to analyze. We then discovered that the DNS ID's for the packets that give this above error message changes. For example, a query is sent by a host machine for google.com, that query gets assigned an ID of 12345, the response comes back with an ID of 34212. The Firewall then blocks the response because of the ID mismatch.

Another interesting thing we discovered was that the hex value for the DNS ID flips. query = e0 1c, response = 1c e0.

Has anyone seen this behavior before? I've double checked and triple check my DNS configuration and everything looks fine. Root hints are being used to resolve internet names if that matters.

I have not come across this (infact i don't deal with Pix/ASA anymore).

The only thing that i am thinking is Connection timeouts. As the DNS request goes out the state/xlat is maintained ready for the return traffic, if the reply took longer then the timeout then the firewall may not know about it and therefore generate these errors

Just a thought