I backed up my iPhone 5 on iOS 7.1.3 last night, today I got a new iPhone 5 with iOS 6 on it. When I went to restore from iCloud upon turning on device, it won't let me because all my back ups are on iOS 7, not iOS 6 which new iPhone 5 has factory installed.
Set up your iPhone 5 as a new iPhone, skipping all the questions. It doesn't really matter what settings you give since they will be removed when you restore your backup.
Use iTunes to restore the device to iOS 7 by connecting to iTunes and clicking Restore.
Once this is complete, your device will be on iOS 7 and will go through the setup process. It is during this where you can select to restore from backup, and since your device is on iOS 7, it will allow the backup to be restored.