Interesting. I have a few questions which may point out the problem.
1/ Are you untarring on the same platform as you're tarring on? They may be different versions of tar
(e.g., GNU and old-unix)? If they're different, can you untar on the same box you tarred on?
2/ What happens when you simply gunzip myarchive.tar.gz? Does that work? Maybe your file is being corrupted/truncated. I'm assuming you would notice if the compression generated errors, yes?
Based on the GNU tar source, it will only print that message if find_next_block()
returns 0 prematurely which is usually caused by truncated archive.