Okay, here is some things I might try and prob. they are things that you have tried?. First, have you applied SP2 to ArcServeIT 6.61? Additionally, I was told by a tech, that the SP2 would have to be applied to clients, also, but was unable to seehow that worked, but at anyrate...I would uninstall the client agent from the machines you are backing up, and then reinstall the client agent. Then under the JobStatus icon in AcrServe I would right click on the jobs that are failing, and modify the job. Look through the source listing for the servers you want, and then browse out to then, forcing ArcServe to verify the security of the account used to do the backup, we us an administrator account with full rights, to do our backups. If you are promted for a password, then put one in, and make sure you can see the server / client. Now go into the job settings, I think it is the icon on the right of the stop light (run). Now verify that the settings have not changed, and then resubmit / repack the job. Are any of the backups working? Are all of the clients missing? Try readding the clients, it seems the DB might have lost some of the information about your network. Make sure the ArcServe Server who is running the jobs can see all the clients, perhaps pinging them, it sounds simple, but worth a try. What else has changed on the network?
Hope this helps.
Smurfman