To be fair, I can't imagine that this is a problem that all Android users have. I think it's more likely that a strange collection of circumstances that led to this. I do think it's a problem that Google needs to look into, so maybe I'll submit it.

Prior to this, I'd used the backup data for every Nexus device that's supported it. This time it did not work.