Did you add a samba user with the same name and passwd as the windows user ala:
You want to have user security enabled in smb.conf (generally).
It could be a firewall issue, as some firewalls will block the NetBIOS "surfing" that's required to get to the samba share (sorry that I don't have a more technical explanation). If you have a software firewall enabled on the linux box, turn it off to see if it helps.
It won't hurt to turn on the WINS server in smb.conf, this may help with the netBIOS name resolution.
It's probably just a password issue.