Error: "The following object cannot be found in the selected backup" or "No object found" (4235466)

When trying to perform an Online Restore and selecting to import a file with the DN of the object you would like to restore, you get the following error:

"The following object cannot be found in the selected backup:
<DNofObject>
Select a backup that includes the object"

You have confirmed that the DN is correct. If you try to Find the objects full name you get no items found. Search for the first 2 or 3 characters of the objects name will return a list of similar accounts including the object you are looking for.