I've recently been struggling to access my Ubuntu Samba server from Windows XP clients experiencing intermittent success and at times receiving the message "is not accessible. You might not have permission to use this network resource." Reading through the Samba documentation it appears that the Encrypt Passwords parameter must be set when using Windows clients, read on for the solution...
Encrypt Passwords — This option must be enabled if the clients are connecting from a system with Windows 98, Windows NT 4.0 with Service Pack 3, or other more recent versions of Microsoft Windows. The passwords are transfered between the server and the client in an encrypted format instead of as a plain-text word that can be intercepted. This corresponds to the encrypted passwords option. Refer to Section 23.2.3 Encrypted Passwords for more information about encrypted Samba passwords.
Within the samba config, smb.conf the following line needs to be uncommented/included:
# DNS Proxy - tells Samba whether or not to try to resolve NetBIOS names
# via DNS nslookups. The default is NO.
dns proxy = no
encrypt passwords = true
After restarting samba I no longer experienced any further issues, moral rtfm.