Check your firewall.
Samba needs ports 137 and 138 open for udp packets as well as ports 139 and 445 open for tcp packets.
For 'smbclient -L \\server' to respond, you will also want to accept udp packets sourced from port 137.
Code:
$IPTABLES -A INPUT -i $EXTIF -s 10.1.1.1/27 -p udp --sport 137 -j ACCEPT
$IPTABLES -A INPUT -i $EXTIF -s 10.1.1.1/27 -p udp --dport 137 -j ACCEPT
$IPTABLES -A INPUT -i $EXTIF -s 10.1.1.1/27 -p udp --dport 138 -j ACCEPT
$IPTABLES -A INPUT -i $EXTIF -s 10.1.1.1/27 -p tcp --dport 139 -j ACCEPT
$IPTABLES -A INPUT -i $EXTIF -s 10.1.1.1/27 -p tcp --dport 445 -j ACCEPT
The above are the lines from my firewall script that allow connections to my Samba server from my local 10.1.1 network.
Edit: Just saw your other post. It looks as though the firewall may not be the issue. Have you created a linux user AND Samba user with the same user name as that being used on your Windows clients?