I've been advocating colored coins since 2012, and the most common criticism I'm hearing from crypto-savvy people is along these lines:
This isn't an improvement over a centralized solution, as you need to trust the issuer anyway. No need to bloat the blockchain.
This is true, if you assume that trust is a binary relationship: you either trust the issuer or you don't. Easy, eh?
But the reality is a bit more complex. You might trust that the issuer actually has money in his bank account, but you don't trust him to have an unbreakable trading system. See: BitStamp. People still use it, so apparently, they believe that it's still solvent. But it have demonstrated that its trading system (particularly, the hot wallet part) is not unbreakable. (Yes, their old system was broken, the new one is surely better :) .)
So, in practice, it is desirable to use a system which relies on a minimal set of security assumptions and requires as little trust as needed. E.g. a fiat<->bitcoin exchange needs to take care of fiat side, but it doesn't need to hold bitcoins, and it cannot have a hot wallet vulnerability if it doesn't hold any bitcoins. Moreover, the fiat side also benefits from a transparent, persistent, immutable ledger.
But the security benefits of colored coins are not as interesting as protocols which can be built on top of them.
Let's consider a Bitcoin-based remittance use case: Alice lives in US, wants to send money to Bob, who is in Kenya. Alice will buy bitcoins with her US dollars, send them to Bob, who will deposit them into one of Kenyan Bitcoin exchanges and will sell them for shillings.
This sounds good in theory (Bitcoin transfers are almost free!), but in practice you have a problem: on top of fees taken by exchanges, parties are exposed to Bitcoin volatility. Kenyan exchange does not trust US exchange (if they trusted each other, they could as well use US dollars for settlements), and so it will require several confirmations. And, as we know, Bitcoin price might drop as much as 10% in matter of hours. So why would Alice and Bob risk their money to Bitcoin volatility? Might as well use WU.
With colored coin atomic transactions, we can implement a transfer with a deterministic exchange rate without any additional trust requirements. Here's the setup we use:
Alice have already deposited USD into US-exchange and currently holds USD-coins
Claire trusts US-exch and wants to purchase USD-coins using bitcoins
Dave holds KES-coins from Kenyan exchange and wants to buy bitcoins
Now let's assume these parties can use some communication medium to find each other and transfer pieces of data (this exchange medium can be either centralized or decentralized, this doesn't affect security aspects of the protocol).
Thus they can create and sign a transaction with tree inputs and three outputs:
100 USD-coins from Alice
0.5 BTC from Claire
9000 KES-coins from Dave
100 USD-coins to Claire
0.5 BTC to Dave
9000 KES-coins to Bob
As you can see, quantities of coins of each kind are preserved, and in the end each party receives what he wants.
The exchange rate (90 KES for 1 USD in this example) is known before the transaction is signed, and if it doesn't suit Alice and Bob they can either wait or use other service.
A basic implementation might be susceptible to double-spend DoS attacks: e.g. if Bitcoin price goes up, Claire has an incentive to double-spend her bitcoins to get them back and sell them at a higher price. To prevent this, funds might be locked via multi-sig in advance.
Also exchanges might use multi-sig to make sure that only entities which went through AML/KYC procedures can hold balance in fiat currencies.
Thus we can conceptually understand it as two trades: 1) USD<->bitcoin happening on US-exchange between Alice and Claire; 2) KES<->bitcoin happening on Kenyan exchange between Bob and Dave which are both tied to a single Bitcoin transaction. If that transaction is confirmed, then both trades are confirmed as well. If it is not confirmed (e.g. double-spend), then none of trades happen. This way we can ensure atomicity across two exchanges which do not trust each other.
An interesting question is whether this can be done without colored coins. In principle, yes, exchanges might make the trade conditional on whether a Bitcoin transaction is confirmed (that would be a transaction from Claire to Dave). But then we have a problem with a race condition: what if transaction does not happen? E.g.
Alice, Claire, Dave submit their orders
Exchanges make conditional trades, blocks everyone's funds
For some reason, a transaction from Claire to Dave doesn't get into the blockchain
After some time, exchange releases Alice's coins, and they are involved in other trad
3 hours later, Claire->Dave transaction is published
So Claire sent her bitcoins, but got nothing in return
To avoid this kind of a problem, we need to make sure that Claire->Dave transaction cannot happen when Alice's funds are unblocked, and to do that, we can represent Alice's funds as a transaction output... Which is exactly what colored coins are about. Basically, by representing everyone's funds as Bitcoin outputs we can create a solution which isn't prone to any synchronization problems, as Bitcoin rules make sure that outputs can be spent only once.