I think the a simple way to resolve this is to add a (optional) group id to the marks. Then each group gets its own column. If no group is given then just throw it into a default group and show the last mark that was set for each line. The API would only get slightly more complex, and optionally no more complex, and conflicts would be avoided for things that care to avoid them.

As for the look of the SCM marks, I do like color on the marks as they are easier to scan quickly. I kind of like the way Atom looks: it keeps the single-column nature of the marks and seems pretty easy to do with simple vectors.