My boss had his iPhone replaced under warranty by Apple. The microphone had quit working. I made a final iCloud backup right before we opened the Fedex package. When I went to restore from iCloud, it could not find any backups. I was very perplexed. I looked at the old phone and verified that it did have a backup and it did. I then thought I would backup the phone to iTunes and then restore from the iTunes backup (it is faster to do this as well). I then found the root of the issue. The refurbished phone was on iOS 5.0.1 and the backup was made on iOS 5.1. There should be a way around this (for non technical people). I wonder if iCloud restore could apply the software iOS version before restoring? The only current way to resolve the problem is to set up the phone as new and then apply the iOS update. Once the update is finished, you simply restore the phone to new and then restore from the iCloud backup.