OK, after going over a few tests with OutCast3k we think we nailed the issue.
In a nutshell:
Currently the order of the signatures matters.
Our tests involved a 2-of-2 multisig address, which I created with 2 pubkeys (lets call them pub1 and pub2).
When spending from the multisig address, signing the transaction with priv1 first and priv2 second always failed when broadcasting (with TX rejected).
But when signing the same transaction in the opposite order, using priv2 first and priv1 secondly the broadcast worked OK.

Thanks OutCast3k for spending a considerable amount of time in troubleshooting this!
