When a CA with NameConstraints is in the truststore, it causes a failure with any crypto Cert provider. The underlying cause is an IllegalArgumentException thrown because the Sequence data has been encoded as an Octet String and it is not being correctly decoded.
While the relevant RFCs are a bit ambiguous with regard to extensions and whether they are all encoded as Octet Strings or not, the documentation on Java's implementation of X509Extension are unambiguous: it will be a "DER-encoded OCTET string for the extension value.
Beneath this issue lies another, the fact that the Sun default implementation of PKIX path validation does not support TrustAnchors with NameConstraints attached. So fixing the first issue also requires conditionally constructing TrustAnchors with NameConstraints or with null.