People having coins of different colors can exchange them securely via a simple bitcoin transaction which would be atomic.

E.g. one person gives 1 red coin and gets 5 blue coins, other person gives 5 blue coins and gets 1 red coins, they construct a transaction, sign it, and once it is in blockchain trade is done. (If one person signs but other doesn't transaction would be invalid. If there is a double-spend, it would also invalidate whole txn. So trade transactions are in fact more secure than accepting bitcoins.)

So what's left is order matching logic, i.e. allowing person which is willing to trade red coins for blue coins to find a person who wants the opposite.

This is fairly simple to implement and straightforward.