Strange DNS problem

At a basic level the problem is that [from a laptop] I can perform an nslookup on an IP and on the coorosponding hostname and receive responses. I can also ping by IP and receive a response but if I ping by hostname or FQDN I receive an error stating "could not find host". If I run an "ipconfig /flushdns" "ipconfig /registerdns" it resolves the issue for a period of time but then it returns.

I am running a Windows 2008 R2 domain with integrated DNS connected to a SonicWALL firewall. The firewall is providing DHCP services and issuing IPs to the wireless devices that are having the problem. While the problem is happening, I can look at the DNS server and see the A and PR records for both the laptop I am using and the server I am trying to connect to. The problem is occuring on both Windows 7 and Windows 8 machines. THe problem has only presented itself within the last two months.

Are you attempting to ping a PC name on the LAN or an FQDN of some non-local domain.name?

hmm; DHCP from an independent device while you have a local DNS service??? Not a good idea.
Your DHCP & DNS services should be coordinated (your DHCP hands out the address of your DNS). For non-local dns queries then your service performs a recursive lookup to a PUBLIC DNS server, eg your ISP's.