It seems to be a rather unusual problem, I have only found it in two more threads and no of them has a solution or a explanation of the problem.
And, as there is no document with error message descriptions avialable for end users (as far as I know). Maybe there is something in the online error message file (omni.cat) but this file is not readable, I can find the message string in the file but can't get the link to a description.
If I should guess something I belive there is some problem with the positions, the information about what is backed up is OK but not where on the media it is located. Therefore DP must search from the beginning until it find something to restore. But, it is only a guessing.
Maybe you should open a support call to HP, there must be documents for internal use where the problem is described.
I have seen this error when there has been processes hanging from failed/aborted sessions.
We used to get this lots of times it was very irritating.
I think it is when you backup part of a filesystem in one datalist and back up another part of the filesystem in different one. But, when you try to restore, you forget that and try and restore the wrong part of the fileystem from the session (the first session will have backed up the directory for the second session so you can select the wrong one). DP can, of course still browse it all OK because it does have all the information but not as part of the session you are trying to restore.
This all comes about if you have no way of linking an object to a session, for example if you never use the Description field but let DP use it's default of the filesystem name.
I hope this makes some sense because when we stopped doing this, we stopped getting the errors.
One of our solutions was to have virtual hosts for each part of a filesystem we were backing up thus the "restore sessions" would have this virtual host name in it's description. This was before it suddenly became obvious that you could just start using the description field itself.
Never preceed any demonstration with anything more predictive than "watch this"