I was getting the same error message. Drove me crazy until i found that my destination path was invalid.
Zipalign will give you that error even if the apk is perfectly valid, but
- the path to the apk is invalid
- the destination is invalid or does not
exists - the permissions are invalid (apk is locked by other program)