Does any data get backed up? Is name resolution working in both directions between the media server and remote NetWare server?
You could try loading the agent into debug mode using BESTART -ZL. Run another backup to reproduce the error and then post back here with sys:\bkupexec\log\ndmpd.log.