[Samba] AD authentication issue in Samba (kerberos errors)

[linux.il]

I have CENTOS7 box with Samba 4.8.3-4  and SSSD 1.16.2-13, authentication
against MS Win domain.
- Recently, Active Directory authentication stopped working within Samba
- Users who try to connect to reach the point of being prompted for AD
credentials; failures happen afterward.
- All flavors of client OS are affected: Windows, Mac and Linux (via
smbclient).
- There have been no configuration changes to the system
(especially/notably smb.conf) in 3+ weeks
- AD and SSSD continue to work fine within the operating system itself (SSH
to the server works, can query AD for group information via ‘getent group
GROUP’, etc.).

I do see some Kerberos errors into Samba logs:

[2019/03/20 09:43:48.594230,  0]
../source3/libads/kerberos_util.c:74(ads_kinit_password)
  kerberos_kinit_password LINUX$@EXAMPLE.COM failed: Preauthentication
failed

As far as I see from forum suggestions, linux box re-join to the domain
should fix this issue, but I'm really don't like such manual workaround.