We've turned on kerberos logging on the domain controler, and we have no error in the system log.
The domain controler is a Windows 2000 SP4 computer with a French version of Windows, limited by design to 58-bit channel encryption. I may be wrong but it seems that the Windows 2000 High Encryption Pack (128-bit) is not available for a french version of Windows 2000 server. The best choice here would be to upgrade to Windows 2003 and see if this solves the problem.