Weird GZip problem

Whenever I try to unzip most any recent tar.gz like such:
tar -xzvf foo.tar.gz

i get this error:
gzip: stdin is encrypted -- get newer version of gzip

or

gzip: stdin is a a multi-part gzip file -- get newer version of gzip

i have downloaded and installed the latest version of gzip, 1.2.4a, but the problem persists, what is wrong?