Como explicado por 'druuna' em link , isso pode acontecer se na verdade é um arquivo ZIP em vez de um arquivo gz, apenas com uma extensão enganosa.
No meu caso, isso é exatamente correto:
$ file tmp.gz
tmp.gz: Zip archive data, at least v2.0 to extract
e usando unzip
em vez de gzip -d
funcionou perfeitamente.