I think we had the same problem and found that the index server needed to be restarted.
In Reply to John Mattson:
I am able to retrieve an item from PDMLink by just typing in the file name in the File-Open dialog in Pro/E. Another user is not. This other user does have permissions to the file, because he can navigate to the file in PDMLink then open it, but not just a retrieve by file name. Why would it work for me, but not him?
Thanks, John