You mentioned that you double-checked the passwords, but what about the usernames ?
Windows98 uses the username and password provided at the logon window in order to connect to shares.
The win98 password has to be the same as the Samba and Linux password.
I suggest you create user names in lowercase only.
Also, I believe there is a patch for networking issues in Windows98, check the WindowsUpdate for any fixes.
There is a step by step configuration available in the OpenBook Using Samba, 2nd Edition
Hope this helps.