Hello everyone, we spent few days trying to find the issue and FINALLY we were able to pinpoint the problem and get the fix done.
In our case (please note that there maybe more issues on your side) we had the incorrect order inside <ds:X509IssuerName> tag.
Because we generated this list ourselves, we were not thinking that this field is somehow important (especially at the time of implementation there were no check at all). The issue start appearing after some release of SDK and changes from ZATCA side without prior explanation what they changed or added.
Long story short, after changing the order from
'DC=local, DC=gov, DC=extgazt, CN=TSZEINVOICE-SubCA-1'
to
'CN=TSZEINVOICE-SubCA-1, DC=extgazt, DC=gov, DC=local'
The issue has been solved. 
I am pretty sure that the validation of this field is: it should be 100% the same as ZATCA generated it using some rules which are not documented. Probably they are getting it from Certificate as a string, but in our case we generate all components of issuer and then combine them together.
Cheers! If you still have the issue, post here the UBLExtensions tag part of your XML and we will try to help you guys.
Best regards,
Sergei