I have just changed my phone from an iPhone 4S to an iPhone 5S. I backed up my old phone to iCloud, then downloaded the backup to my new device.
Whilst entering the settings app in my new phone, it asked me for the password to an Apple ID that was not mine. It transpired there was an app on my old phone that had been downloaded using this other ID. The app did not appear in "my purchases" in the App Store and the phone has never belonged to anyone else. It has only ever been backed up to iCloud or a secure iTunes account on my laptop.
How is this possible? I spoke with Apple and they couldn't help.