Have you tried creating a new key, if that fails I would remove B4A and everything do to with it, make sure your java is update date then reinstall B4A 7.8 with the newest SDK and try again.
I'm sorry but formatting your computer is NOT an option and is 100% overkill, also does it work in Debug mode?