Android - What's the cause of "Application not installed" error?

The exceptions coming from zip (in the log extract) indicate that the package is corrupt. This error could have been introduced by the download, or when the package file was generated. You could check for download errors by verifying the APK file's SHA-1 or MD5 checksum against a checksum provided by the download site. Obviously each site will have a different way of telling you the checksum. Also, the method of verifying it is different depending on what OS your PC runs: on Linux it's as simple as running md5sum file or sha1sum file.

Note that this won't always be the case from the "Application not installed" error message. As others have indicated, that message usually results from trying to install a package that already exists on the system, unless the new package has a newer version number and is signed by the same key.