Hello,
After installing the hotfix, had you reinstalled the legacy Unix agent? If not, reinstall it and then try the backup.
Although you have mentioned that 'The information in hosts and resolv.conf is correct' , you can reverify it as per the steps in the technote below:
Title:Backup of Unix/Linux server fails with error "Final error: 0xe000fe29 - Authentication failed on connection to the server. Make sure that the user account has the appropriate permissions and that the password was typed correctly" even though the logon account has sufficient rights on the Unix/Linux machine
http://support.veritas.com/docs/272987
Are you using 10.0 5484, if yes, it will be a better idea to upgrade to 10.0 5520 from the following link:
http://support.veritas.com/docs/277181
You need to reinstall all the remote agents after the upgrade.
Do update if the above helps.
Note : If we do not receive your reply within two business days, this post would be marked ‘assumed answered’ and would be moved to ‘answered questions’ pool.
Regards.