How to restore iPhone 5 from iOS 5 backup?
I have restored plenty of iOS 5 backups onto iOS 6 devices so the problem here is almost certainly that the backup is now (and may have been all along) corrupt.

Before throwing that backup away and restoring the iTunes files from a backup of the computer where it was stored (hopefully you have that), you could try restoring the backup onto another device such as a borrowed iPad or iPod touch (or iPhone) to be sure it's not the phone you are restoring the backup to.

The article iTunes: About iOS backups will help you locate where your computer stored this backup set as well as general info to support the idea that you can back up an older OS onto a newer OS (but not the other way around).