I just tried creating a new key in Construct 3 and doing a signed release APK build with it. It worked fine.
One thing that may be at work here is IIRC the keytool used by the server does not support using a different password for the key and the keystore. For this reason we removed the option to use two different passwords when creating a keystore in Construct. But we made this change some time ago and it's been in place for some time. We preserved the option to specify separate passwords when using an existing keystore though, for backwards compatibility with existing keystores. Since then we haven't changed anything apart from the target SDK version, since Google require that, and as far as I can see the signing process still works, at least with a newly created key.
I'm afraid I can't comment on third-party software - whether or not it works is out of our control and we can't be held responsible for it, so it may be more fruitful to get in touch with the developer of the tool you use.