If it hasn't already been implemented/suggested, I would point out a new transaction type is needed: One party announces that they have traded a number of BTC for a number of colored coin of a specified type, and the other party confirms. That would allow a user to buy colored coin from a third-party reseller without needing to trust the reseller.

This usecase is possible right now. Technically. That is, I can execute this counterparty-risk-free trade right now by typing commands into the console. And this is using the standard bitcoin software that doesn't even have the faintest idea what a 'colored coin' is. This is the kind of possibility that intrigues me about bitcoin. I care next to nothing about the currency itself but the potential use of the infrastructure to solve other tasks through clever combination of known cryptographic primitives is enormous.

For curiosity's sake, a sketch of how your use case can be implemented as a transaction is:

• Each transaction consists of a list of input transactions and a list of outputs. (The amount of bitcoin going to each output is specified, for inputs the entire amount of bitcoin from each input transaction is used.)
• Colored coins are just plain old bitcoins that happen to have a signature stamped on a transaction somewhere in the history of that coin. Clients not familiar with such markings---as well as miners storing the transactions---treat them the same way as all other coins.
• When colored coins are combined in a transaction with uncolored coins, the colored coin protocol is defined such that the first outputs are the first outputs get the colored coins and the uncolored coins go to the remaining outputs.
• Either party A or party B can create a transaction in which a bunch of bitcoins from an address owned by A and a bunch of colored coins owned by B go to addresses owned by A and B (with the A output going first).
• After the first party creates the transaction and signs it with the relevant signature it can send it to the other party.
• The second party signs it as well and sends it off to be added to the bitchain.
• Without both signatures the transaction is worthless.
• With both signatures the entire trade takes place in a single transaction. Neither party needs to trust the other.