Running backup returns the following error:
Connecting to remote server outlook.office365.com failed with the following error message : Access is denied. For more information, see the about_Remote_Troubleshooting Help topic.
Retype your password for the service account and start the jobs again.
This is due to changes with the service account. After such a change, the backup service cannot decrypt the service account credentials stored within the configuration DB, and needs to be refreshed.