From LQWiki

Troubleshooting

If you are setting up a linux box to act as a router, and you have a windows box going through it that can ping the outside world but DNS is mysteriously not working, and all you see are some strange NETBIOS messages when you ping a domain name, try manually setting the DNS server entry on your windows box to point to your linux box and it may start working.

External Links

http://www.zytrax.com/books/dns/ch7/