You can use the "verify-only" restore option (available both in Qubes
Manager and on the command-line) immediately after creating a backup.
That is the problem. I have done the verify and it passes with no error for all of the backup archives that have problems restoring my "storage" AppVM. As I discovered this has been a problem for nearly 4 months worth of backups.
I am trying to find if there is another way to verify backups because the built in method and restorting is failing me at the moment. Or better fix the backup/restore issue