I almost did but I tried something else and found the likely reason: the file name contained an "ä". Par2deep also fails when there's a CJK character in the filename. After removing these non-ascii characters it works. But this bug is going to cause problems for many people.

Edit: filed a bug report