Attualmente io sto usando la 8u66 e non ho questi problemi ma non sono molto convinto che il problema possa essere la tua versione, successiva.
Io proverei a creare un nuovo keystore, assicurandomi di aver dato al progetto un package name corretto.
Potrei inviarti il mio file di java, ma qui non potrei allegarlo, essendo troppo "pesante". Probabilmente potresti trovarlo su siti non ufficiali (magari qualcuno sufficientemente affidabile!!!) ma perché non registrarsi sul sito di Oracle? Mi sembra più sicuro.
Dai anche un'occhiata (e magari pubblica qui) al testo che trovi in:
(è una casella di testo editabile, per cui posizionati su essa, CTRL+A per selezionare tutto, CTRL+C per copiare nella cllipboard di Windows).