Is colored coins not introducing an additional layer of trust?
That depends on how you define "another layer of trust".
Colored coins are inherently used for tracking things outside the blockchain - that by definition means representing obligations a.k.a counterparty risk. Any technique that tracks obligations outside the blockchain will be tracking counterparty risk.
But none of that has nothing to do with the underlying technology used to create the token. Colored coins as tokens are no different from other bitcoins. A colored coin token doesn't all of a sudden become less trustworthy than a non-colored Bitcoin.
I define "another layer of trust" as trusting anything else but the Bitcoin network.
In that regard colored coins are less decentralized than sidechains.
I don't get sidechains. Will they just be alt-coins then?
Sidechains have two models. They are effectively an alt-chain that is supported by the BTC unit on a 1:1 peg.*
In the proposed concept, they use a SPV client to settle between chains. To secure the chain they would use merged-mining which potentially lets them access 100% of Bitcoin's mining power. They are not quite as secure though as they are not accepted by all nodes.
They can also use a less-decentralized model that rely on Oracles/Federations/Voting Pools.
*the unit is technically not the actual BTC but an image of it locked in a multi-sig type of way. the peg could also be a deterministic function but that defeats the purpose and effectively creates an altcoin.
Is there a new innovation in merged mining that adds some security?
The security for merged mined side chains is more likely to be based on good will, than merged mining. The "can't be evil" requirement is really the critical element. (Our collective effort to maintain the non-evil is the guiding principle of this topic.)
Everyone has to pretty much love the SC like a precious offspring, for it to survive, if it is merge mined. Otherwise merge.mine.capability will more likely kill it rather than secure it.