I was at the Apple store last night to get my 4S replaced (on/off switch broke) and the replacement unit they gave me had iOS 5 installed. When I was presented with the option to restore from iCloud backups, my old 4S backup (iOS 6) did not appear. The genius upgraded the software on the new phone to iOS 6 and then I was able to restore from iCloud.
Not sure if that's supposed to be that way but my experience implies that you should upgrade prior.