I'll start looking for a Samba Howto. In the meantime, I thought I would see if this error message meant anything specific to anyone on the list.
That's a pretty generic error. Before you tear out too much hair, make sure that turning off iptables (service iptables stop) doesn't fix the problem.
Also, try accessing the samba server diretly by IP address to make sure that it isn't a name-resolution issue.