Corrupt password issue

I'm having an odd issue with a 10.3.9 xServe. It's being used as a bog-standard file share server using just AFP - local dir only, not LDAP. For some reason, at random, the server will refuse to accept a user's login details to the share point. This happens across all users at random. There are no special settings (password expire, etc.) As I say is just being used as a basic vanilla fileshare solution. Any ideas???