Hi Simon,
If you go into Backup Exec, and go to Tools\Install Remote Agents, you can install multiple remote agents to servers. If you are installing AOFO, then they will all need to be rebooted after the install.
As far as uninstalling the previous version first, this is not necessary, however, I would recommend it just to be safe. There is no mass uninstall procedure, though, so that would have to be done individually on each server; but like I said, it's not required.
Please let us know if this helps resolve your issue.
Thanks.