When trying to assign or reassign a parent directly on a work item or using bulk update, user receives "No Items Found". The user has access to the child work item and both parents. This can happen on a story, a parent on a feature or other portfolio item type.
This is due to the search index taking a bit to load from the server.
Type or paste the parent ID into the search and allow 5 to 10 seconds for the search index to populate. The parent will populate once the search index has loaded.