It could be that Backup Exec has some form of corruption in its database / files. I find that occasionally I get Media servers that suddenly stop behaving properly and they do similar things. Sometimes they just don't start their backup jobs, for no reason.
I find the quickest way to deal with problems like this is to perform a complete uninstall of Backup Exec, reboot the server, re-install Backup Exec and manually re-write the backup jobs.
Obviously you have to make sure you write down all the job configurations beforehand.
I look after 58 media servers and 200 remote servers with approx 6.5TB of data backed up each night across nearly 300 backup jobs. I keep everything documented and through plenty of practise I can have backup Exec uninstalled, re-installed and configured in less than an hour on all servers. This makes is much quicker sometimes than looking for the solution to odd problems such as yours.
Hope this helps.