I recently upgraded am iPhone 3GS to iOS 5.1. A week later, the phone started acting badly. I succeeded in backing it up, then tried to reapply the firmware, and it would not update, leaving me with an effectively dead phone. I took it to apple and ultimately I very unhappily ended up paying $160 for a refurbished phone which came with iOS 5.0. When I went to restore the phone from iCloud it reported that there were no available backups. Huh? I know that there are backups. On a hunch I setup the phone as a new phone, updated it to 5.1, then erased it, and tried to setup and restore from iCloud again and this time is saw all the backups.
Interesting lesson. iOS 5.0 cannot see iOS 5.1 backups.