Samba- "Preauthentication failed" every time the machine password changes

Issue

As per the default winbind settings, every week the machine account password is changed on our rhel8.9 hosts. However, every week when this happens we soon afterwards get 'Preauthentication failed' messages in the logs and users report they can't log in.

[2024/07/31 15:51:43.156481,  0] ../../source3/libsmb/trusts_util.c:626(trust_pw_change)
  2024/07/31 15:51:43 : trust_pw_change(EXAMPLE): Verified new password remotely using netlogon_creds_cli:CLI[RHELCLIENT/RHELCLIENT$]/SRV[adserver01/EXAMPLE]
..snip..
[2024/07/31 16:32:10.008227,  0] ../../source3/libads/kerberos_util.c:74(ads_kinit_password)
  kerberos_kinit_password RHELCLIENT$@example.com failed: Preauthentication failed