Snow Leopard doesn't like dnsmasq?

I'm using dnsmasq via Tomato on my home router and and haven't run into any issues with Snow Leopard.

How do you know that queries from the Macs are going though your server? Can you see the requests in the logs? If so, what do requests for hosts on the local network look like, do they show up in the logs at all?

Look at Network preferences, Advanced, DNS tab. Make sure that there are no editable (black) entries. The only DNS servers listed should be ones provided by your DHCP server and including your local server.

Also try doing your tests through dscacheutil instead of nslookup, this'll make sure you're seeing the same results as other applications on the computer. You can perform a query like this:

dscacheutil -q host -a name <hostname>

Also try flushing the local DNS cache:

dscacheutil -flushcache