Normally I wouldn't bother making a blog that probably only applies to MOSS 2007. But while solving for this error message . . .
You must first restore the original list in order to restore the folder
Troubleshoot issues with Windows SharePoint Services.
. . . I was surprised at how there was just no information anywhere on this error anywhere. Figuring someone will run into this, I thought I'd fill the gap.
The problem and fix were ultimately quite simple. A site collection owner had deleted a document library, recreated the library manually, and then attempted to restore the documents and folders from the recycle bin. But he couldn't restore from the recycle bin. He got the error. The administrator then tried to restore folders or files from the recycle bin and got the same error message. ULS logs were not useful at all.
The problem was that we didn't know exactly what the site collection owner had done. We didn't know he had recreated the document library. So the Admin didn't know to look harder in the recycle bin for the doc lib. After deleting the new doclib he could restore the old doclib and proceed to restore the documents and folders.