Domain users can't access Windows server from their Macs

I have a Win2003 SBS Domain server/file server that I'm trying to access from a few macs that aren't on Active Directory, but are connected to my network.

Attempting to open a network share as one of my domain users gives me "Connection Failed: You do not have permission to access this server"

However, I can access the share just fine if I login as a domain administrator. These domain users can also access these shares correctly from a domain PC.

I'm not sure why I'm having these permissions issues.

I've tried both username and domain\username.

Using just username works fine with my domain admin account.

Also, note that if the Mac user types in his domain credentials wrong, he gets an "invalid username/password". If the mac user types in the password correctly, he gets the "Connection Failed: You do not have permission to access this server", which means that the windows server is at least validating the password. I just need to know how/where to give them proper permissions.