Can I restore data backed up from a newer version of iOS? I have a 3gs with iOS 5.1.  I backed up my data, and wanted to restore to my new iPhone 4, with iOS 5.0.1.  Somehow, I was not given an option to restore my backup.  Is it possible to restore backup to a device that has older firmware?
Unfortunately you cannot restore an iOS device to any backup that had been done from a newer version of iOS, using either iCloud or iTunes, due to the firmware. 
iTunes will give an error and iCloud will not even show the backup as an option to restore from. 

To be able to use the backup that you have, you must upgrade the iPhone 4 to the newest 5.1.1 update that was just released. It should go smooth from there. 

I work at the Genius Bar at an Apple Store.