Server(s) and clients all upgraded or mixed NBU versions?
Did you verify compatibily before the upgrade (O/S and SQL versions)?
Are filesystem backups going through?
Do you have NBU logs on the client? To start, bpcd is necessary to troubleshoot connectivity issues.
dbclient log is required to test SQL backup issues.