All instances of storage metadata are corrupted

It’s important first to understand what the “storage metadata” is.
 
The storage metadata is akin to an MFT (master file table) for the Veeam Backup & Replication backup file. The storage metadata informs Veeam Backup & Replication which blocks within the backup file belong to which file that was backed up. It is stored within the backup file twice for redundancy, and only one entry is ever modified at a time. If both storage metadata entries become corrupt, Veeam cannot determine which blocks belong to which original files that were backed up.
 
There are many potential causes for this issue; the majority are related to either storage failure or a communication issue with the storage device.

Due to the nature of the storage metadata, once it becomes corrupted there is no way to restore from the file.
 
If this error occurs during a restore:
If you are using the 3-2-1 rule (see below), attempt the restore from a restore point from a different backup set for that day.
 
If this error occurs during a backup job:
Please start a new backup set for the specific job that is failing with this error. Details on how to start a new backup set can be found in KB 1885.
 
Moving forward. it is highly advised to use SureBackup to test backup validity.
 
There is also a Validator command line tool that can be found in the installation folder of Veeam called, Veeam.Backup.Validator.exe. This tool can be used to Validate consistency of backup files.
 
It is also advised to periodically run CHKDSK, or an equivalent function against the location where the backup files are stored.

http://www.veeam.com/blog/how-to-follow-the-3-2-1-backup-rule-with-veeam-backup-replication.html

Related forum post:
http://forums.veeam.com/veeam-backup-replication-f2/all-instances-of-the-storage-metadata-are-corrupted-t2228.html#p92839