I found this was caused by my JDK version.
I was having this problem with 'ant' and it was due to this CAUTION mentioned in the documentation:
http://developer.android.com/guide/publishing/app-signing.html#signapp
Caution: As of JDK 7, the default signing algorithim has changed, requiring you to specify the signature and digest algorithims (-sigalg and -digestalg) when you sign an APK.
I have JDK 7. In my Ant log, I used -v for verbose and it showed
$ ant -Dadb.device.arg=-d -v release install
[signjar] Executing 'C:\Program Files\Java\jdk1.7.0_03\bin\jarsigner.exe' with arguments:
[signjar] '-keystore'
[signjar] 'C:\cygwin\home\Chloe\pairfinder\release.keystore'
[signjar] '-signedjar'
[signjar] 'C:\cygwin\home\Chloe\pairfinder\bin\PairFinder-release-unaligned.apk'
[signjar] 'C:\cygwin\home\Chloe\pairfinder\bin\PairFinder-release-unsigned.apk'
[signjar] 'mykey'
[exec] pkg: /data/local/tmp/PairFinder-release.apk
[exec] Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES]
I signed the JAR manually and zipaligned it, but it gave a slightly different error:
$ "$JAVA_HOME"/bin/jarsigner -sigalg MD5withRSA -digestalg SHA1 -keystore release.keystore -signedjar bin/PairFinder-release-unaligned.apk bin/PairFinder-release-unsigned.apk mykey
$ zipalign -v -f 4 bin/PairFinder-release-unaligned.apk bin/PairFinder-release.apk
$ adb -d install -r bin/PairFinder-release.apk
pkg: /data/local/tmp/PairFinder-release.apk
Failure [INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES]
641 KB/s (52620 bytes in 0.080s)
I found that answered here.
How to deal with INSTALL_PARSE_FAILED_INCONSISTENT_CERTIFICATES without uninstallation
I only needed to uninstall it and then it worked!
$ adb -d uninstall com.kizbit.pairfinder
Success
$ adb -d install -r bin/PairFinder-release.apk
pkg: /data/local/tmp/PairFinder-release.apk
Success
641 KB/s (52620 bytes in 0.080s)
Now I only need modify the build.xml to use those options when signing!
Ok here it is: C:\Program Files\Java\android-sdk\tools\ant\build.xml
<signjar
sigalg="MD5withRSA"
digestalg="SHA1"
jar="${out.packaged.file}"
signedjar="${out.unaligned.file}"
keystore="${key.store}"
storepass="${key.store.password}"
alias="${key.alias}"
keypass="${key.alias.password}"
verbose="${verbose}" />