Verifique se você não possui dois fatores de autenticação na conta usada para o Directory Sync. Se você ativou recentemente, isso explicaria o problema.
Além disso, lembre-se de que as senhas expiram periodicamente por padrão no Office 365. Assim, a sincronização do diretório será encerrada periodicamente e exigirá intervenção manual.
Tente conectar-se ao Office 365 com o PowerShell usando a mesma conta e veja se você recebe um erro.
Como prática recomendada geral, você deve criar uma conta de administrador dedicada na nuvem apenas para o Directory Sync.