We had the same problem with many stored procedures that did multi-row inserts.  It was all thanks to the "improvements" they made in the optimizer (Cardinality Estimator specifically, IIRC).  We "patched" the problem by using the Trace Flag that says to use the old CE.  Unfortunately, that also means that our "get out of the woods patch" has become the fix because people don't understand that we actually do need to tweek,n,peak the inserts and won't even try to fix them.