I have the same problem here to...
backup exec 12.5 sp3
windows 2003 sp2
ibm 3623-2lx
Backup worked fine on fresh install off version 12.5
I then updated to latest service pack 3, and backup jobb started failing.
Autoloader went offline atleast onc...