Operation Could Not Be Performed – Object's Parent Uninstantiated Or Deleted

When trying to restore an AD object, you get this error:

The operation could not be performed because the object’s parent is either uninstantiated or deleted

You get this error because you are trying to restore an AD object to an AD container, OU or other object or directory structure that has been deleted from AD (or is in a state that cannot contain that object).

To fix this, reinstantiate / restore the parent object. Alternatively (I haven’t tried this), you might try using the Restore To option instead of restoring the object to its original parent.