I have a similar if not the same issue. This happens with my backup-to-disk jobs.
The job status is missed, and the error is "e000e020 - The job was scheduled to run, but the availability window closed before the job could start. There may not have been any destination devices available during the window, or the job may have been submitted to run when the window was closed."
The only thing that I can think of that changed was the account that is used to do the mailbox backups. (permissions issue). Each time I log into the BEWS, and check a job, I have to enter in the credentials of this account.
Any ideas? Even the jobs that is set to "overwrite" are missed.
In Job Summary Information, the original start time is 1hr later than the "job started" time.
There's a hotfix here but am wary as it doesn't really have a clear description: http://seer.entsupport.symantec.com/docs/287164.htmnull