samba - Feb 2002 - Re security passwd-encryption & netbios-names (wins)-RH 7.2 samba 221a (standard installation from rpm)

How is your win box resolving names to ip addresses.  If you are not using 
wins then I think you need to setup a valid lmhosts file on your win box.

Or setup one wins server on the linux box and use static ip addresses on both.

See if that helps