0xe0008516 Veritas BackupExec Error with Exchange 2007

I started getting the following error on my Exchange 2007 backup using Veritas 12.5:

Completed status: Failed Final error: 0xe0008516 - Resources specified for snapshot do not have any valid data on them. Check if files were deleted or renamed.

Here are the steps I tried:

1. Reinstalled backup exec agent on mail server.
2. Isolated the information store into its own backup, separate of the system state, c drive etc.
3. Removed the Exchange license, rebooted media server and re-added it.
4. Rebooted the media server.

None of those steps worked. Then, I remembered I created new storage groups on the Exchange server. They did not have anything in them. I made them and was going to move mailbox databases into them but never got around to doing it. As soon as I unchecked the unused storage groups, the backup completed successfully.