I think there are two ways of looking at this.
One of them is compatibility of the conversion – given the same Markdown, the implementation produces the same HTML as the reference implementation(s). In the optimal case, this is equivalent to “the implementation matches the spec” and “the implementation passes all the tests”.
If this is the case, then by all means the implementation should be considered compatible, as @codinghorror says.
The second view is a similarity in how it’s implemented compared to the reference implementation. For example, you could probably create a CommonMark-compatible converter that works similar to John Gruber’s original Markdown implementation, which is a bunch of regex replacements with some extra logic inside it. And you could also create a CommonMark-compatible converter whose inner logic works similar to the CM reference implementation, including an identically-structured document tree (see “Appendix A: A parsing strategy” in the spec).*
Such a similarity would have the advantage that extensions could be ported between implementations in a fairly straightforward way. Say you have a CommonMark implementation in LISP that creates the same kind of document tree for its intermediate representation, and there’s some sort of plugin that processes this tree in some way before it’s passed to the HTML renderer. This plugin could probably be easily ported to, say, the JavaScript reference implementation. On the other hand, you could have a CommonMark implementation in Fortran that uses regular expression replacements similar to Gruber’s Perl original. Since this Fortran implementation has no comparable intermediate document tree, the plugin couldn’t easily be ported to work in it.
So the Fortran implementation should by all means considered CM-compatible, but the LISP implementation has an additional nice-to-have level of compatibility. I don’t know that we need to have a name for this additional level, but it’s something to keep in mind.
Of course a plugin written for a Ruby implementation that uses a similar regex replacement technique could be easily ported to the Fortran version, so this kind of “compatibility” doesn’t only apply to the reference implementations.
*or how ever else the final CM reference implementation may eventually work