Are you providing them DNS from an internal server? If so, it may be giving them an (inaccessible) internal-only address when resolving your comapny's Internet-facing servers.
In any case break it down:
- what IP addresses are they trying to reach when their requests fail?
- is their route to those addresses via the Pix's inside interface?
- is there any access-list on the Pix inside interface that is preventing the traffic from passing?
- does the Pix outside interface know how to reach those addresses?
