I recently installed dnsmasq on my linux box. Everything seems to be working ok locally--I changed the resolv.conf to show that the loopback address is the nameserver and when I do an nslookup (locally) I get a very quick reply:
The problem I have is when I set a Windows box on the same LAN to use the Linux box as the DNS server. NSLookup on my Windows box results in timeout errors and the address never resolves.
I have set up Shorewall to open requests to port 53 and I can successfully telnet into port 53, so I don't think it is a firewall issue.