Is this causing the failed message?
Yes.
my backups, which are set to start at 11:30pm, are starting later and later
It's a window of time, not a set-in-stone start time.
It sounds like something is happening on your network. Is someone else doing backups?
Is someone doing maintenance of the network (taking it offline maybe)?
If the backups are failing all the time, did someone remove Backup Exec's permissions to the files? Was the share removed?
Brian