Did you install the client on your mail server?
What operating system? Are you running selinux? Is there anything in the netbackup logs directory, I think by default /usr/openv/netbackup/logs/
We're pretty sure we know what the problem is at this point. I'm running 64bit everything (rehat, zimbra) and apparently symantec is still working on support for intel chips atm.
For some reason the client install was not updating the correct files. We installed the netbackup server, uninstalled it then installed the client. After this the service started. Wierd, but it's working.