I once had similar problems that were caused by double or not compressed files - I can't precisely remember which way. Anyway, I solved the problem by running all files through gzip (or was it gunzip?) -- after renaming them of course. Maybe your situation is similar.
BTW I don't think you have to rename the files before processing them with tar. Only gzip requires certain suffixes. BTW2: All of these hassles can be avoided by using the atool utilities, which figure out how the files are compressed and how to uncompress them.