I have exactly the same problem! Yes, I have read the manual and it's no help.
What I did notice though was a slight difference in the sever names. Our Domino server is called AUMELDMS01/FEA and in Arcserve the Domino server is shown in the server tree as Lotus Domino Server - AUMELDMS01/FEA. When I tried to run a backup the error in the log stated the agent name as \\AUMELDMS01\dbanotes@AUMELDMS01\
Note that the "FEA" is missing off the end of the server name.
OK, so me thinks "Let's have a look in the Registry on the Notes server" Making a backup of the registry first of course!!
Under HKLM\SOFTWARE\ComputerAssociates\BrightStor ARCserve Backup\DSAgent\CurrentVersion\agent\ I notice the entry dbanotes@AUMELDMS01/FEA
Inside this key is an entry called "name" (this was Lotus Domino Server-AUMELDMS01/FEA)and another called "PreviousInstanceName" (this was blank)
So, as an experiment I renamed the "name" key to "Lotus Domino Server-AUMELDMS01/" and "PreviousInstanceName" to "Lotus Domino Server-AUMELDMS01/FEA".
I then renamed the key (removed the "FEA" bit at the end) to HKLM\SOFTWARE\ComputerAssociates\BrightStor ARCserve Backup\DSAgent\CurrentVersion\agent\dbanotes@AUMELDMS01/
Confused yet??
I then tried a restore and it worked!! The manual mentions something about not changing the Domino server name otherwise you need to specify it in the "PreviousInstanceName" in the registry.
The strange part of all this is that I've never changed my server name. The only changes I've made is upgrade Arcserve from V9 to V11.1
Just in case you are now totally confused, basically, all I've done is rename the server name for the agent and put the old server name in the PreviousInstanceName entry.
I haven't tried doing a backup yet but I'll get back to you if I have issues.
Hope this helps you out.
Cheers!