Are you absolutely sure you're getting the right file downloaded? I've had problems before where, due to my adblocking filters or some misconfiguration in the servers, the file I get is actually an .html or .php file or something.
Also, at least if you're using KDE, don't trust Konqueror's "file type" column. It only reads the file's extension. But the file "properties" should give you the real type.
You can also double-check what a file really is by running "file filename.zip" in a console.