I am not familiar with windows DNS issues
check out your hosts.conf and of course the resolv.conf
If you have a local domain you can create the file defaultdomain on the linux client if there are multipule networks.
Are you really sure windows is giving you the right IP ... or IP at all
After all I've seen recently some XP machine just giving up their winsock32 libraries ... very strange behavior... As metter of fact it seemed to be a virus and the windows boxes couldn't make socket-connections anymore
Stupid M$!
Do you use firewall or perhaps iptables/chains on the linux side so that the queries are blocked
what did you put in your /etc/networking/interfaces file or whatever is the equivalent on your systems
very strange
regards