I just got a replacement for my 4S. Before, I did an iCloud backup and thought I could just restore from that. But with the new phone, it says there's no backup to restore from available.
Ask Different is a question and answer site for power users of Apple hardware and software. It only takes a minute to sign up.Sign up to join this community
Backups are generally portable across any and all iOS device. Could the new device be at a lower software level? Try an over the air update to ios 5.0.1 and also be sure everything is exact in the account. firstname.lastname@example.org is not always the same as email@example.com.