All backups couldn't run and all the clients had moved from the left hand side (Clients) to the right hand side (Available NVBU Machines) in Client Management, because the NetVault Server license had corrupted somehow.
We could confirm this as there was an expired error message when launching the Backup and Restore windows.
We re-installed the NetVault Server license key and all the Clients returned to the left hand side under the Clients window.
All the backups are now running again as well.
Note: If you no longer have the NetVault Server license key (or any other license key), click on the following TIMS Portal link and enter in your details:
http://license.quest.com/machineid/reset
Once all items have been filled in, then the relevant license key will be emailed to you.
