First, I must clarify that I had to uninstall BE after upgrading to 5520 due to some really strange problems. After I uninstalled this, I re-installed a fresh copy of 5520. Is there anyway that this could have caused my problems. I thought maybe it was possible that the "older" 9.x versions worked with the legacy unix agent and upgrading those version kept that functionality and then once I installed a fresh version of 10 v5520 without the upgrade, I lost this.
I have tried your suggestions below. I re-installed the agent located at C:\Program Files\Veritas\Backup Exec\NT\Agents\Legacy Unix Agent and also added entries in both computers hosts files. I also restarted both BE and the unix agent after doing this. This still gave me the same error I mentioned above.
I am able to see the linux computers in my backup selections and I can select files to backup, but after I start the backup it errors out.