I have set up shares on the Windows 2000 and RedHat 9 sides of my network, and I can access the windows shares from linux (and transfer files, etc.). I can click the Liux machine and SEE the linux shares from Nertwork Neighborhood, but when I click on the Linux share I get a "Incorrect Password or unknown Username for \\Linuxhostname\sharename" then there's a "Connect As:" and "Password:" box. I am POSITIVE that My Windows login and password are identical and I have also set up an IDENTICAL smbpasswd for the same username. Passwords are encrypted.

post your /etc/samba/smb.conf.

I believe encrypt passwords = yes needs to be under the global section in order for it to work, too.