What language $L \in NCM$ has $\overline{L} \not \in NCM$?
Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement.  First, it is indeed recognized by a NCM — as is the complement of the language of palindromes.  The NCM simply ensures that two positions in the input word chosen non deterministically hold different letters, and checks that they are separated by exactly half the length of the input.

Now Parikh Automata were introduced by Klaedkte and Rueß in ICALP'03.  The technical report version, available on Klaedkte's webpage, states the equivalence of Parikh Automata and NCM as Theorem 29 and 31.

Relying on a combinatorial argument, they show that the complement of $L$ is not recognizable by a Parikh automaton, Lemma 26.  Further lemmata have been developed to show that some languages are outside this class (we present a few in this journal paper).