Thank you for your reply jschiwal,
I'm running FC5, and Samba was installed as a binary using yum. I tested just using "valid users = sa", where sa is my username, and still - I'm unable to login.
The strange thing is, root can always log in.
When login fails, this gets added to syslog
Apr 8 14:51:19 fedora smbd: [2006/04/08 14:51:19, 0] smbd/service.c:make_connection_snum(592)
Apr 8 14:51:19 fedora smbd: Can't become connected user!