What I could recomend is that you go directly to the servers with the agents installed and manually uninstall them, and have the agent installed through the CD or the upgrade package that you originally used. You'll find it under WINNT\INSTALL\ENG\I386\NTAA\setupaa.cmd.
Make sure that the agent has been successfully removed and rebooted just to make sure that the registry and the memory is cleared. Once the agent has been successfully installed you may need to reboot the server again. Once this has been completed, make sure that the services on the Logon tab has also been changed accordingly, then stop and restert the services to apply the changes to the services.
After these setps have been successfully performed test the backup server with a system state backup of the remote server. This will confirm several tests at once if the system actually backs up the system then it will mean that the services has access to the file systems and also means that the agent is also working correctly.
Good Luck.