It sounds to me like they lost some sort of master reference table that maps customers to services, instances, data, and so on. Which would mean a lot of manual examination to recreate the map. And would give you that situation where maybe the first thirds of restores is somewhat "fast" because it's the bigger customers with more data/logs/activity, and so easier to identify. But now they've hit the long tail.

They may also be gated by limitations in-between customers and the backups. Like backups going through a transit VPC, for example. You don't see the bandwidth limitation when you're sending incrementals all day, but try and do full, parallel, multiple customer restores through it, and ... (and perhaps they are afraid of making too many changes on top of the current chaos to fix something like that)