I'm having the very same problem with a recent version of Puppy Linux
(supposedly binary-compatible with Ubuntu Lucid). I've replaced sharutils,
tar and bzip2 with the "vanilla" ubuntu packages, but still not luck.
bunzip2 -tvv gives me the following error: "bag magic number (file not
created by bzip2)"