I have just installed Samba for the first time ever yesterday, and also answered a forum post on an issue.
It appear that Samba need to resolve netbios names to tcpip - at least if I follow the walkthrough from the pcllinux magazine, sep. 09.
As both me and the forum poster got Samba working just fine adding nss_wins I suggest to include it as a dependency to Samba client.
Tried to find other ways/documentation - but couldn't find any, let me know if there is another way of setting it up (i.e. without wins) - meanwhile I'll alter the samba client package,