As long as the remote SQL server is SQL 2000 with SP3a or newer you shouldn't have a problem.
Always make a backup of the Catalogs and Data folder on the current Backup server (stop BE services, stop SQL instance and copy C:\Program Files\Veritas\Backup Exec\NT\Catalogs and Data folders)