40 fish!? This does *sound* like an infection... specifically, this sounds a lot like **White Spot** (aka Ich). Check out our existing question https://pets.stackexchange.com/questions/1922/what-exactly-is-ich or [this][1] link with more info and treatment. The 'bruises' may be a secondary infection even. 

As with most fish illnesses- quarantine is the best first step to troubleshooting. I would start a fresh tank for the new Cichlids, but if you can't, follow some of the treatment steps in the link above, but take it slow: environmental changes are always stressful on fish. Be mindful of oxygen changes and temperature (!and pH!) changes.

In my experience cat fish are hardy little beasties, so it might be that their skin type and where they live in the tank plays a role in them not getting sick. They, and your plants may well be contributing factors. I know some plants may be 'carriers' if they've lived in infected tanks before. 


  [1]: http://www.cichlid-forum.com/articles/ich.php