Debes estar combinando el -z y -j opciones de compresión. El primero usa gzip el segundo usa bzip . El comando tar xjvf no te dará ese error.
Mi solución fue instalar bsdtar . No sé por qué el tar normal no funcionaba, pero voy a presentar un informe de error.