You don't mention your distro, your version of samba, etc... so it's a little difficult other than a guess.
Enable WINS support on your samba server, see what happens.
Jon Johnston
Creative Business Solutions
IBM, Microsoft, Novell/Suse and Sophos Consulting
952-544-1108
http://www.cbsol.com
AIM:jonejohnston
Blog:
http://bingo.cbsol.com