It really is quite complicated. In the best case, in my view, there would be specialized clients that would interpret certain classes of transaction scripts, and the majority of wallet software would not care at all, and only acknowledge the basic transactions (pay to pubkey hash). But all miners have to be aware of the full scope, and all full nodes will need to have some extra complexity, in order to even validate the blockchain. That complexity leads to unpredictable behavior and bugs. My guess is that when Bitcoin really has to go head-to-head with another coin, this "feature" will have a dragging effect.
I glanced at the papers on http://coloredcoins.org, and they haven't changed. Though the colored coins are tracked through the blockchain, the fact that a coin is colored, and what that color means, lives entirely outside the blockchain. My analogy with "smart property" simply looking for a particular serial numbered bill is very apt, but of course you gain the cryptographic anti-counterfeiting guarantees of bitcoin. All the same risks apply as well; you can inadvertently spend a colored coin, and if the recipient is not looking out for it, they'll probably never know that they are in nominal possession of a colored coin, and possession of the "smart property" will simply float around between people, just like a similarly-marked dollar bill inserted into a vending machine would do.