Managed Backups are failing

Managed Backups are failing systematically with the following error:
"Aw shucks, something went wrong :slight_frown: Instead of the beautiful response we expected, we got this:
Other kind of backup error"

We have tried refreshing the API key, increasing memory and adding Snapshot constants to wp-config.php to backup in smaller chunks, as well as reverting to the previous version of the plugin (3.0.4) but Managed Backups keep failing.

The last Managed Backup that completed as scheduled was on June 11th. Note that Snapshots are working, but Managed Backups are not.