Windows – Snow Leopard and a Windows network

This is not an actual fix to your problem, but it should eliminate the headaches that you are experiencing.

A. Create a folder called "Network Shares" or somewhere in your user directory or possibly in a shared directory. Drag this directory to the finder sidebar under Places.

B. Do the following for each share that you want to connect to routinely:

1. Use Command-K from finder to mount the shared volume. This should add the server under shared in the finder sidebar
2. Go to System Preferences -> Acoounts (Under System), select your account and open the login items tab.
3. Click the plus button under login items and navigate to the share that you want to connect to.
4. This gets a little tricky here. For some reason, you cannot create an alias in finder (Command-Option Click and drag) to network shares, you can do this to any directory under the network share, but not the share itself, so if you want the share itself accessible as an alias, you have to use the terminal to create a symlink which is essentially the same thing. If you need to do the symlink thing here are the steps.
5. Make sure that the share is mounted.
6. Open terminal.
7. Navigate tothe folder you created, Network Shares (if you created this folder directly under your home folder the command is cd ~/"Network Shares"/.
8. create the symlink :ln -s /Volumes/"Share Name" "Name of alias file" (the quotes aren't necessary if there are no spaces in the file name.

What you end up with is a folder full of aliases that point to all the shares you access frequently.

This is a name resolution problem, but not exactly DNS unless your NAS box has a fully qualified domain name. The Macs that are visible on the network under the Finder's shared category are discovered through Bonjour and Multicast DNS. I'm not sure exactly what OS X uses for discovery of SMB shares.

It sounds like the Non-Connecting Mac can discover the SMB shares through multicast, but is not getting the correct IP address information. You might try the arp command from the terminal to see what IP address is returned for the name of the NAS box. If the NAS box is named "nas.local" then the command would be:

arp nas.local

and it will return the IP address associated with nas.local in the Mac's ARP cache.

You might try nmblookup to see what sort of SMB information the Mac is receiving. I'm not real familiar with it but I think the command might be:

nmblookup -n nas.local

The samba man page will give you more options and information.

I've seen problems for years with connecting to servers through the sidebar and never nailed down a sure fix for them. You mentioned all machines are on DHCP. You might put the NAS box on a static IP. You could then drop an entry into /etc/hosts for nas.local. That's not ideal but it might be an easy fix for just a couple of computers.