Thanks to Quinn and i_82 for the helpful investigation above.
This can happen with modern Java. Perhaps the mysterious change was a Java upgrade and not a macOS change? The cause is Security.framework falling behind the evolution of PKCS#12 security standards. Newer tools generate key stores encrypted with "modern" algorithms like AES, but macOS/iOS only understand key stores encrypted with long since broken and obsolete algorithms like SHA1 and TripleDES.
To fix it you have to change the Java security properties file (or use Security.setProperty in code), as follows:
keystore.pkcs12.keyProtectionAlgorithm = PBEWithSHA1AndDESede
keystore.pkcs12.certProtectionAlgorithm = PBEWithSHA1AndRC2_40
keystore.pkcs12.macAlgorithm = HmacPBESHA1
Once these are set, generated p12 files will be Apple-compatible.