Our users are seeing this issue, and it is preventing them from access our samba server. We are currently using samba v3.4.2, and kerberos 1.7. It is authenticating against Windows 2008R2 domain controllers.

Samba config:
[root@bb02smb01 samba]# more /usr/local/samba/lib/smb.conf
[global]
	security = ADS
        workgroup = CARYNT
        realm = NA.SAS.COM
	netbios aliases = dntsrc tstsrc
        password server = *
        allow trusted domains = Yes
        socket options = TCP_NODELAY SO_RCVBUF=65536 SO_SNDBUF=65536
        encrypt passwords = yes
        winbind use default domain = Yes
        nt acl support = Yes
        server string = PC Bubble Samba Server
        winbind enum users = No
        winbind enum groups = No
        winbind cache time = 300
        idmap uid = 70000-99999
        idmap gid = 70000-99999
        map acl inherit = Yes
        preferred master = No
        local master = No
        domain master = No
        log file = /var/log/samba/%m.log
        max log size = 10240
        client use spnego = Yes
        server signing = auto
        deadtime = 15
        max smbd processes = 5000
        dns proxy = No
        oplocks = No
	#smb ports = 139
	log level = 3
	#use kerberos keytab = yes
	kerberos method = system keytab

Error log:

tail -300 /var/log/samba/__ffff_10.17.12.5.log

2010/02/23 11:03:23,  1] smbd/service.c:1226(close_cnum)
  __ffff_10.17.12.5 (::ffff:10.17.12.5) closed connection to service tst
[2010/02/23 11:03:34,  1] lib/util_tdb.c:521(tdb_wrap_log)
  tdb(/usr/local/samba/var/locks/mutex.tdb): tdb_lock failed on list 2 ltype=1 (Interrupted system call)
[2010/02/23 11:03:34,  0] lib/util_tdb.c:69(tdb_chainlock_with_timeout_internal)
  tdb_chainlock_with_timeout_internal: alarm (10) timed out for key replay cache mutex in tdb /usr/local/samba/var/locks/mutex.tdb
[2010/02/23 11:03:34,  1] lib/server_mutex.c:71(grab_named_mutex)
  Could not get the lock for replay cache mutex
[2010/02/23 11:03:34,  1] libads/kerberos_verify.c:496(ads_verify_ticket)
  ads_verify_ticket: unable to protect replay cache with mutex.
[2010/02/23 11:03:34,  1] smbd/sesssetup.c:342(reply_spnego_kerberos)
  Failed to verify incoming ticket with error NT_STATUS_LOGON_FAILURE!
[2010/02/23 11:03:34,  1] smbd/service.c:1047(make_connection_snum)
  __ffff_10.17.12.5 (::ffff:10.17.12.5) signed connect to service tst initially as user cates (uid=709, gid=100) (pid 16299)
[2010/02/23 11:03:34,  1] smbd/service.c:1226(close_cnum)
  __ffff_10.17.12.5 (::ffff:10.17.12.5) closed connection to service tst
[2010/02/23 11:03:45,  1] lib/util_tdb.c:521(tdb_wrap_log)
  tdb(/usr/local/samba/var/locks/mutex.tdb): tdb_lock failed on list 2 ltype=1 (Interrupted system call)
[2010/02/23 11:03:45,  0] lib/util_tdb.c:69(tdb_chainlock_with_timeout_internal)
  tdb_chainlock_with_timeout_internal: alarm (10) timed out for key replay cache mutex in tdb /usr/local/samba/var/locks/mutex.tdb
[2010/02/23 11:03:45,  1] lib/server_mutex.c:71(grab_named_mutex)
  Could not get the lock for replay cache mutex
[2010/02/23 11:03:45,  1] libads/kerberos_verify.c:496(ads_verify_ticket)
  ads_verify_ticket: unable to protect replay cache with mutex.
[2010/02/23 11:03:45,  1] smbd/sesssetup.c:342(reply_spnego_kerberos)
  Failed to verify incoming ticket with error NT_STATUS_LOGON_FAILURE!
[2010/02/23 11:03:50,  1] smbd/service.c:1047(make_connection_snum)
  __ffff_10.17.12.5 (::ffff:10.17.12.5) signed connect to service tst initially as user cates (uid=709, gid=100) (pid 16413)