I ran a search on the messages you pasted above and found two known causes of this issue.
There is an issue in Avamar client version 6.0.100-592 that can cause this problem. I believe you mentioned that these clients are running version 6.1.101-87 so this is probably not the cause of the problem. Please double check to make sure all the clients in the MOSS farm have the same Avamar client version installed and that they are running 6.1.101-87 or newer.
Another possible cause of this problem is that the clients in the MOSS farm have multiple network cards and are trying to communicate using the wrong networks. You can force the Avamar client agent to bind to a specific IP address by creating a file called "avagent.cmd" in the Avamar var directory (C:\Program Files\avs\var by default) and adding the following line (replace 192.168.x.x with the correct IP address for your environment):
Once the file has been created, you will have to restart the Avamar backup agent (at an elevated command prompt, run "net stop avbackup" then "net start avbackup" or use the Services snap-in).
Normally the back-end client is where this change needs to be made.
If this does not resolve the issue, I would recommend opening a service request. If you open an SR, please provide zip files of the logs from each of the clients in the farm. Make a note of which set of logs is from which client and the role of each client (front-end or back-end).
Hope this helps.