To solve this, I removed the existing backup plans and storage accounts, then ran options > repository > Shrink Database.

This seemed to clear everything out. Then I rebuilt the backup plans, and setup the storage accounts, all is working as normal now.

One note, I created new containers in the storage accounts so they'd have their own indexing, separate from the previous generation.