Need to do this on an unsigned apk file...
I ran into this same problem for an android apk using Eclipse. I don't know if your running into the exact same problem. But, I'm guessing the principles are similar.
To fix this I had to do the jarsigner on an unsigned apk file. If you are using Eclipse, the apk is signed with a temporary key (which I think the android market won't allow).
If your using something else, you can see if your apk is already signed using syntax like:
$ jarsigner -verify -verbose my_application.apk
To get an unsigned apk in Eclipse, right click on application name in the Package Explorer window and choose Android Tools, then choose "Export Unsigned Application Package...". Save the package to a new location.
Once you have an unsigned apk. Run the jarsigner command you were using on the unsigned apk file.
This is also possibly explained better (at least for an android user using Eclipse) at:
Like I said earlier if your not using Eclipse to generate an apk, possibly the tool your using has similar options to create an unsigned apk file.