I just worked on this same issue for someone else at work (iPhone 4 or 4S up to date). The iPhone 5 needs to be up to date to the newest version of IOS
Here is what I did:
1. Got into the iPhone 5 without using an account
2. After getting in, it shows that there is an update
3. Completed the update
4. After the phone rebooted, went in and completed a reset of the phone to factory
5. When it came back up followed prompts and was able to restore from iCloud backup.
Hope this helps