It's the KYC that scares users away from these exchanges and this Changelly is just one that asks KYC. I was surprised about this accusation though but I found the exchange reputable because once upon a time CMC had been promoting as an affiliate. I could be wrong about this but I have seen it before where they have a signup button on CMC going to Changelly.
Coinmarketcap has been noted to promote lots of scam and shady ICO before. The community have been calling them out for years, so seeing Changelly being promoted by coinmarketcap doesn't mean that we can trust them.
But I do agree that once they implemented KYC, many crypto enthusiast started to move away from their services. Besides, there are a lot of options now, unlike before where there are less competitions and so they became one of the game changers.
A reputable exchange asks for KYC upfront and that's it. A disreputable one like Changelly springs it on you whenever it feels like it and uses it as an excuse to hide behind. Monero users in particular have had a lot of trouble and Changelly have openly stated they will keep your money if you don't satisfy them.
And look at this fairly new accusations against them,
https://bitcointalk.org/index.php?topic=5251793.0.