Hi.
1. I'm surprised by the answers about the issues with the library and s.o. During initial phase NBU doesn't know what robot will be used finally. Job is started, put to the queue and then master is going to seek for resources based on policy/STU and s.o. In case of any issue with robot there has to be either failed job or job in waiting state.
2. With the command "nbpemreq -predict_all -date <mm/dd/yyy hh:mm:ss> -policy_filter <policy>" you can see what is scheduled for this policy. If there are no jobs, you can have old stuck jobs that are not in jobdb anymore but NBU stil think that they didn't finish and cannot start new job. Check whether in output of "nbpemreq -jobs screen all" are not some old jobs. Then contact Symantec - they will navigate you to stop NBU, delete some explicit files and folders and start NBU.
Anyway. It will not be - probably - your issue as with these symptomps you can stil run backup manually.
3. Check if there are no trunning a lot of bprd processes on master. (I hope it's bprd, don't remember exactly). Just run "bpps" and if there is few hundreds of jobs of the same daemon BUT without any command line argumens (like details about particular backup job) it can be an issue. Restart of NBU on master helps.
4. Or really you have corrupted NBU installation as described in previous answer.