Is the server you are trying to restore to in a cluster? If so, maybe the data you think is on the cluster is actually there at the time:
Example:
Servers in a cluster: N1, N2, N3, N4
data on the cluster: data1, data2, data3, data4
Normal setup on the cluster
With that said, you did a backup and it worked. Now you need to restore file.x
when you open your admin console to choose "source client/policy time and the destination clients"
you may be thinking the file.x "when backed up" was on
\\n1\data1\file.x which it was, but, data1, which contains file.x may not be on n1, but in fact may be on n3.
so for the destination client you need to choose n3
you can verify that through whatever means you have, but from the message I see, that you cannot restore to the destination server, this is what I assume.
Hope this helps...if not, my bad