Password Self-Service > AD > G Suite sync

Hello

We are experiencing a weird issue with PSS and G Suite.
When the user is first enrolled for PSS and attempt to change their password for the first time, it seems that Google does not pick it up correctly. Users are still able to log in to domain PCs (AD) but when trying to log in to their Google account, they cannot.
Google says that the password was changed, but does not allow to log in with either new or old password.

When they run the procedure again, all works suddenly. 😲

We went through all possible logs to trace any errors but all looks perfect.

Did anyone come across this issue?

We are expecting over 2000 students to enrol during the summer and we need to fix this.
Help, please.