We've had a java app on the MAS since late summer 2012. I think we were the first java app on the store (more info at infinitekind.com).
I think one issue is how you are signing. To be accepted on the app store you'll need to bundle a JDK. This can be done using the appbundler ant task. We've created a fork of this with a few improvements since the official one seems to be stagnant and not accepting updates:
https://bitbucket.org/infinitekind/appbundler
We've also created a fork of the OpenJDK with a couple of minor fixes that were dealbreakers (menu item keyboard shortcut issues) for us. These may now have been incorporated into the mainline OpenJDK, but I don't think so.
https://bitbucket.org/infinitekind/openjdk7u-jdk
Anyway, the above two items may not be necessary in your case, but that's how we did it and it worked. I think the real problem is what you are signing and in which order. Here's what we do and it's been accepted for five update submissions now:
# sign all the jar and dylib files (signing jars is apparently not required by apple, but should be!)
find "Path/To/App/AppName.app/Contents" -type f \( -name "*.jar" -or -name "*.dylib" \) -exec codesign -f -s '3rd Party Mac Developer Application: YourCompanyName' --entitlements 'path/to/AppName.entitlements' {} \;
# Sign the JDK plugin
codesign --verbose -f -s '3rd Party Mac Developer Application: YourCompanyName' --entitlements 'path/to/AppName.entitlements' "Path/To/App/AppName.app/Contents/Plugins/jdk"
# sign the whole bundle
codesign --verbose -f -s '3rd Party Mac Developer Application: YourCompanyName' --entitlements 'path/to/AppName.entitlements' "Path/To/App/AppName.app"
Hope this isn't too late to be helpful!