Filesystem Backup Fails with 'Failed to validate segment data for backup, record was not updated'. (4036554)

Filesystem Backup Fails with 'Failed to validate segment data for backup, record was not updated'.

The NetVault Server was upgraded to NetVault Backup 10 a while ago and had recently crashed.
Since that crash, some backup jobs to a VTL were failing with the following errors:

1] Job Message   2014/08/26 02:48:38   739   Data Plugin   kateprod3   Storing backup index
2] Error   2014/08/26 02:48:39   739   Media   netvault-intern   Failed to validate segment data for backup, record was not updated
3] Error   2014/08/26 02:48:40   739   Media   netvault-intern   Failed to add backup record
4] Error   2014/08/26 02:48:40   739   Data Plugin   kateprod3   Failed to write backup index to the database
5] Severe Error   2014/08/26 02:48:40   739   Data Plugin   kateprod3   Failed when finalizing the backup
6] Error   2014/08/26 02:48:40   739   Jobs   netvault-intern   Job Status: Backup Failed

There was an issue storing the backup index to the VTL media and/or the NVDB?
Additionally since the NetVault Server crashed, the NetVault Server hadn't shut down correctly and may have corrupted to the NVDB too?

By performing a new Full backup, this creates a new Index in the NVDB and media where the Incremental and Differential can be based upon.
The Full backup ran successfully, so the original Full backup Index had corrupted.