Quite a fun problem.

Installing an application from the JAD says invalid JAR on some Nokias, but installing direct from the JAR works fine.

The problem as it turns out, is that there is a bug on some Nokias where if the version ends in a 0 (i.e 1.1.0), it says its invalid.

Very stupid, and very annoying bug. Thanks Nokia