I've encoutered similar problem with devices 2.1 and 2.2 Using JDK6 didn't help, but manually signing with jarsigner, providing sigalg and digestalg - did (even with JDK7):
jarsigner -sigalg SHA1withDSA -digestalg SHA1 -keystore keystore.keystore file.apk alias