Extracting a *.tar.bz2 file?

You must be combining the -z and -j compression options. The first uses gzip the second uses bzip. The command tar xjvf will not give you that error.

My solution was to install bsdtar. I don't know why the regular tar wasn't working, but I'm going to file a bug report.