The error can mean 2 things depending on what file you downloaded. In the normal sense, when users download a file not ending with .gz it means the file is not a gzip format.
The other case is when the downloaded file is corrupted. I took my time to download the http://www.djangoproject.com/download/1.4/tarball/
file and it works with the line you are mentioning so it must mean the file was downloaded and somehow got corrupted. Download the file again.
Just to add that I had a problem about a year ago, similar to this, it was a memory problem. One of the memory slots was damaged (Memtest verified this). This is of course an extreme case, but wanted to mention it just in case.
What I would suggest is to do the following:
Download file like this: wget http://www.djangoproject.com/download/1.4/tarball/ -O Django-1.4.tar.gz
(No double quotes, just in case when copied from a website, they were the bbcode double codes and not the common ones used in the terminal)
Decompress like you mentioned: tar xzvf Django-1.4.tar.gz
See if that works.