This can happen sometimes when service account passwords are changed in AD and Managed Account passwords stored in SharePoint are now out of sync. Fixing this is fairly easy, not sure if the documentation on this is pretty clear but this may help others
Fortunately we can fix this with a simple PowerShell
$cred = Get-Credential($Account)
Write-Host -ForegroundColor White "Updating Stored Managed Account Password"
Set-SPManagedAccount -UseExistingPassword -Identity $Account -ExistingPassword $cred.Password