I have this problem on windohs clients if I do not add a lmhosts file into the windows directory, once I do that all other computers are seen through network Neihbourhood.
Incedentially I can still access the computers by manually typing in their ip/computer name, they just dont appear in the NN until I copy in the LMHosts file, or in NT/2K/XP I have to copy it over then under network settings import the file.
This is due in whole to the isolation of Window's Name Bindery information from my remote LAN's.
Normally, each Windows stations (NT or 95/98) broadcasts its existence onto the LAN at regular intervals. These broadcasts remain local to the LAN segment and would not be propogated over the Internet to the remote server, or vice versa. As such, the mapping that would normally occur between server (or workstation) name to IP Address has to be accomplished in other manners. This is where the LMHOST file comes in.
Located in the Windows directory of every workstation is a file called LMHOSTS.SAM. This file presents a sample configuration of a properly configured LMHOST file. Essentially, this file maps a workstation/server name to an IP address.
On the client workstations, the LMHOST file would require an entry for the name of the server and the IP Address used to reach it. Remember, if NAT is being used, the IP Address entered here will be the address of the server-side router.
For additional details configuring the LMHOST file, the Microsoft Support web site is a valuable source of information. One article available on their web site is "How to Write an LMHOSTS file for Domain Validation".
http://support.microsoft.com/support/kb/articles/q180/0/94.asp?FR=0