When you delete something, it goes into trash.
.Trash-$UID/files/TrashedFile.ext
.Trash-$UID/info/TrashedFile.ext.trashinfo
The trashinfo contains the path relative to .Trash-$UID's parent directory that is the location to which the trashed file or directory should be restored.
Imagine accidentally trashing 1000 files, and at some point rmdir the containing directory before you realize you need to restore the trash.
In Ubuntu 12.04, no problem, the .trashinfo path would be created when restoring the trash if it didn't exist.
In Ubuntu 12.10, you get 1000 popups saying "There was an error getting information about the destination. Details: Error when getting information for file '/mountpoint/path/to/file': No such file or directory."
For every popup, you can manually do a mkdir -p '/mountpoint/path/to/file', hit "RETRY" and it will work.
Something has changed in the past 11 months that SERIOUSLY cripples the handling of trash.
I am not sure this bug is in the right place, or that something else handles the trash for Nautilus. Nemo, fork of Nautilus, has the same problem. If not filed correctly, please think with me where to file this in the right place, because it's pretty important.
Correction: I don't know if 12.04 had that problem. I just remembered I had Lubuntu, and when I try pcmanfm now (just installed on 12.10), it does NOT have this trash problem.
So work-around for restoring trash when parent-directories are also removed: Use PcManFM for handling the trash.