The fix worked for me with a couple of additional steps, so in full here is what I did:
1. Stop Backup Exec services
2. Go to \Symantec\Backup Exec\Data folder
3. Search for files with CRT file extension. Move files you found (4 pcs) to another folder.
4. Search for files with KEY file extension. Move files you found (4 pcs) to another folder.
5. Start BE services.
6. Open a selection list, drill down through Domains and then Microsoft Windows Network and right-click the remote agent server and select "establish trust relationship".
Important! Remember to repeat step 6 with every agent computer you have! Backups wont work otherwise.
7. Then drill down to Windows Systems under Favourite Resources, right click and select 'Add Windows Systems' and enter remote server name (Repeat for all affected servers), click refresh and then they should all re-appear.
I have tested backups and restores and these servers are now communicating fine again.
Many thanks for everyone's help!