since you've already mentioned the firewall, i assume you've allowed 10000 and the other veritas ports? if not, see
http://seer.support.veritas.com/docs/194182.htm and
http://seer.support.veritas.com/docs/276538.htm
there are several services involved, on the media server, all the services should be running under the veritas service account that was set up during the install. usually this is a domain account with, at least, backup access on your target servers.
on the target servers, there should be one service, the remote agent (or more, if you have database, exchange or notes agents). remote agents should run under local system. the media server usually has a remote agent.
under the "network" menu, there should be an option "logon accounts". ensure all of these are correctly qualified, including the domain or computer they exist in. these accounts must have at least backup rights to the appropriate target server, per below. also, check the system logon account and make certain it has administrator control on the media server.
on the job setup page, select the job you're having trouble with and double click. go to the resource credentials heading, and ensure each of the target servers has the correct entry from the "logon accounts" page above.
the easiest way to ensure everything is correct is to use the system logon account against all your target servers.