Intermitent DNS Failures

Hi all, I am a new squid administrator due to the person who set up
the box leaving the operation. I am having the following problem and
don't know where to even start looking.

We are running squid 2.5.STATBLE3 on a Slackware 9.1 machine. It is
set to proxy only, no caching. Its been up for about six months
without a problem. Three weeks ago we put up a new firewall and since
them have receiving the following message:

While trying to retreive the URL:http://www.google.com/

The following error was encountered:

Unable to determine IP address from host name for
www.google.com

The dnsserver returned:

Server Failure: The name server was unable to process this
query.

This means that:

The cache was not able to resolve the hostname presented in the URL.
Check if the address is correct.

I can sometime get it working again by recreating swap files (squid
-z), other times I have to shut down and restart squid. It can work
fine for hours without issue, or it can go down every 10 minutes at
other times. If I bypass squid and go out directly to the firewall
there is no problem at all.

Since this started about the same time as the new firewall
implimentation, I am guess that is related, but I have no clue were to
even to start to find the problem, does anyone have any ideas?

Thanks in advance.