I'm very surprised by these comments...
I regularly review code that is way more complicated that it should.
The last few days I was going back and forth on reviews on a function that had originally cyclomatic complexity of 23. Eventually I got it down to 8, but I had to call him into a pair programming session and show him how the complexity could be reduced.
Someone giving work like that should be either junior enough that there is potential for training them, so your time investment is worth it, or managed out.
Or it didn't really matter that the function was complex if the structure of what's surrounding it was robust and testable; just let it be a refactor or bug ticket later.
I know the aggravation of getting a hairball of code to review, but I often hold my nose. At least find a better reason to send it back, like a specific bug.
If you're sure cyclomatic complexity should be minimized, I think you should put such rules in a pre-commit hook or something that runs before a reviewer ever sees the code. You should only have to help with that if someone can't figure out how to make it pass.
If you're not willing or politically able to implement that, you might be wasting time on your personal taste that the team doesn't agree with. Personally I'm pretty skeptical of cyclomatic complexity's usefulness as a metric.