Backup plans instantly failing with code 20,250,685(0x135003D) since upgrade to version 11.5.43994

We noticed a problem with the RDX cartridge used for Wednesdays' backups. The 2015/07/22 and 2015/07/29 backup jobs failed due to an error of "There is not enough space in the backup destination" which appeared to be because Acronis was unable to automatically delete the old backup, for some reason so we manually deleted the old backup and the 2015/08/05 backup job succeeded due to there no longer being an old backup but the 2015/08/12 backup job failed due to the same error.

On 2015/08/13 (yesterday) I contacted Acronis' support and they remoted in, informed me of the following, and upgraded Acronis Backup from version 11.5.38774 to version 11.5.43994:
"Vineet: I think we will have to upgrade this software looks like issue with the tape is caused due to incorrect phrase on XML.
Vineet: Typically, this can be corrected once the product is updated.
Vineet: I can help to update the software right away."

The scheduled 2015/08/13 and all subsequent, manually-run backup jobs to any RDX cartridge (including ones that used to work) are now failing due to the following errors:
"Type: Error
Date and time: 13/08/2015 19:00:02
Backup plan: NightlyFullBackup
Task: Full backup
Code: 20,250,685(0x135003D)
Module: 309
Owner: @
Message:
Command 'Running backup plan 'NightlyFullBackup'' has failed.
Additional info:
--------------------
Error code: 61
Module: 309
LineInfo: 4a8728dc8a1c9510
Fields: $module : mms_vs_43994
Message: Command 'Running backup plan 'NightlyFullBackup'' has failed.
--------------------
Error code: 41
Module: 307
LineInfo: e6792a5ee190ddc0
Fields: $module : agent_protection_addon_vs_43994
Message: Failed to execute the command.
--------------------
Error code: 33
Module: 307
LineInfo: 5d2a9295cc9442e0
Fields: $module : gtob_ensure_backup_invariants_command_addon_vs_43994
Message: EnsureBackupInvariantsCommand: Failed to prepare the location for the backup archive.
--------------------
Error code: 2
Module: 154
LineInfo: 9a79f20828bca35
Fields: IsReturnCode : 1, $module : disk_bundle_vs_43994
Message: Location not found.
--------------------
Error code: 2
Module: 154
LineInfo: 9a79f20828bca35
Fields: $module : disk_bundle_vs_43994
Message: Location not found.
--------------------"

The problem is that the Acronis support expired 2015/08/14 (today), which I was unaware of, so I cannot contact them to get them to fix what they seemingly broke.

Here's some additional information:
1. The user account used for the backup has not had any credential changes.
2. The RDX cartridges are perfectly accessible via Explorer as they used to be.
3. Repairing the installation does not affect the issue.
4. I have obtained an installer for the original version but it doesn't seem to support downgrading, only configuring from scratch which we don't really want to do.

Thanks.

NOTE: I actually fixed this during the process of gathering information for this post but considering how little information I was able to find on the above errors I will post the solution in response to my own post to help future users.