sun/security/provider/certpath/AlgorithmChecker.java:

   350 // Check with previous cert for signature algorithm and public key
   351 if (!constraints.permits(
   352 SIGNATURE_PRIMITIVE_SET,
   353 currSigAlg, prevPubKey, currSigAlgParams)) {
   354 throw new CertPathValidatorException(
   355 "Algorithm constraints check failed on " +
   356 "signature algorithm: " + currSigAlg,
   357 null, null, -1, BasicReason.ALGORITHM_CONSTRAINED);
   358 }

Here, the exception message only mentions currSigAlg but it might be because prevPubKey has not passed the permits check (Ex: it uses a 512-bit RSA key).

Add -Djava.security.debug=certpath and you will see the real reason following with the confusing exception:

certpath: KeySizeConstraints.permits(): RSA
certpath: Constraints: failed key sizeconstraint check 512
Exception in thread "main" java.security.cert.CertPathValidatorException: Algorithm constraints check failed on signature algorithm: SHA256withRSA