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.
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.