See also
this very recent thread.
The JDK variant you're using *may* have an impact.
A definite no-no is: Don't use Java 9, it dropped support for the (old) profile the Kindle needs.
Barring that, I've never had issues with Oracle's JDK, without having to resort to digging out a truly ancient version.
You may need to specify a specific algorithm for the signing process, c.f., KUAL's ant recipe.