iCloud backup from old 4S to new 4S?
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. xxx@mac.com is not always the same as xxx@me.com.