After a Samba server crashed due to a power failure, several users could no longer access it shares. When access was attempted, password dialog was shown and the correct password was not accepted. Strangely, the problem affected only some users, while others continued to work in Samba shares successfully.
The Samba server's /var/log/messages showed the following errors:
May 19 12:48:05 server winbindd[1929]: tdb(/var/lib/samba/winbindd_idmap.tdb): tdb_rec_read bad magic 0x42424242 at offset=102664 May 19 12:48:05 server winbindd[1929]: Error storing SID -> ID: Corrupt database
So, the problem was that windbindd_idmap.tdb file was corrupted. In this situation, the only sensible solution is to restore the file from a backup. If you don't have a backup, you are out of luck. Best you can do is remove the corrupted file, but it stores the mapping between Windows and Unix user IDs, and as the result file ownership and permission information on the Samba shares will be screwed up.