We are experiencing an issue where some of our users are unable to find and set a Parent for an Epic. We have setup Portfolio as seen in this screenshot:

We then setup our Epics to display the Parent Link field (since it is our understanding that Jira/Portfolio require you to set the Parent instead of setting the child). When I open an Epic and search for a "Feature" in the Parent Link field I see everything working as expected and can make the link successfully. However, when some other users attempt the same thing I am doing they are unable to find the "Feature" and see the following:

I assume this is a permission issue but I am unsure which permissions need to be altered. I know we had a similar problem a year ago but the guy that figured it out is no longer with our company, that is why I currently have permissions to set the Parent Link.
One of the people experiencing the problem is our Portfolio admin and I went into Jira and made him an Admin of the Project in question, but that didn't solve the issue. So, short of just going around trying to give him access to everything, I am not sure where to specifically look.
Can anybody help me out with this issue?