What is your Windows network environment - Active Directory, Domain, workgroup? Your Samba server has to be set up in a similar fashion. If you are using Active Directory, I think you will need to explicitly add this machine to your domain using whatever server is handling your AD.
It does sometime seem to take a while for the Windows machine to get locked onto the Samba server. Have you tried explicitly entering the Samba server's name (\\server_abc) from a Windows machine (Add Network Location), rather than relying on the Network Neighborhood approach? That seems to work better, at least initially. Also, you'll want a fixed IP address for the Samba server.
There are some differences between Vista and previous Windows versions regarding what ports are used and what protocols. You might need to tweak some smb.conf settings.