Unknown email password required after selecting iCloud backup
The cause of this problem is very simple and isn't related to privacy issue or "left over ids" from refurbrished devices.

You have PIRATED music in your library.  

When restoring the back-up, iOS tries to authenticate the PIRATED files and realizes the account has been locked down.