It turns out that this error message pops up for one of two other reasons:

The files are named incorrectly or a file is missing. Remember that Linux is case-sensitive and all files in the set should be named similarly. One of the files is damaged and might need to be repaired using GPar2, if you have the matching PAR files.

Here’s the irritating error message.

If you’ve also got the corresponding PAR recovery set files, what you’ll want to do is install GPar2 using the Add/Remove Applications, or by just typing the following command into a terminal prompt:

Then you can just open up any one of the .par2 files and click the Repair button, which will take a fairly long time to complete, but should allow you to extract without errors.

More information on PAR or Parchive files can be found at Wikipedia, of course:

http://en.wikipedia.org/wiki/Parchive