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!

Yup, the order of the signatures seems to matter, I'll currently trying to work out a solution.
Thanks ktorn, for beta testing and finding the issue.
Will post back when fixed.
the order that signatures are added no longer matters.