Search the forum, SP4/SP4a install failing is a known problem. It only happens if service has been applied since backupExec was intgalled. AFAIK, the SP installer was never fixed, but a workaround was provided to someone through a paid incident, who then shared it here. It involves registry diving, but everyone who tried it reported success
See http://forums.veritas.com/discussions/thread.jspa?threadID=55069
if you would rather not edit the registry then you can:
use BEUTIL to save your config to a file See http://seer.support.veritas.com/docs/268315.htm
copy the \catalogs dir to a save area
delete BackupExec
boot
re-install BackupExec
Use BEUtil to recover from a file
copy the \catalogs dir back
see http://seer.support.veritas.com/docs/272886.htm to force BackupExec to reindex the catalogs.