Existing colored coin scheme relies on the order of inputs and outputs:
https://bitcointalk.org/index.php?topic=106373.0;topicseen . There are few problems with this scheme:
1. Signature tag like SIGHASH_ANYONECANPAY cannot be used since the order of inputs in the final transaction is not known.
2. SPV nodes cannot verify colored coins
3. The whole transaction chain could not be pruned
A soft-fork could solve these problems:
1. Redefine OP_NOP3 as OP_CHECKCOLORVERIFY
2. When a user wants to mint colored coin, he sends some coin to an output with a script of
OP_CHECKCOLORVERIFY OP_DROP OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG
where
is defined as
RIPEMD160(SHA256(script of previous output))
For example, if Satoshi wants to create a colored coin with his Genesis Block address 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa, will be
RIPEMD160(SHA256(76a91462e907b15cbf27d5425399ebf6f0fb50ebb88f1888ac)) = 653756a92059ba4f3086471bd3c9e8442e4da3d3
By hashing the whole script, colored coin can be minted out of any future payment scheme
3. It is necessary for Satoshi to sign the minting output to make the whole transaction valid. The transaction is not valid if he is signing with SIGHASH_NONE, or SIGHASH_SINGLE but not for the minting output
4. Redistributing colored coin is done just like normal transaction, with inclusion of OP_CHECKCOLORVERIFY in appropriate outputs. However, the total value a specific colored coin in outputs must be equal to or less than the total value in inputs. If the value in outputs is less than inputs, some color coins turn back to normal BTC. The only exception is Satoshi decided to mint more colored coin with his address, so the total colored output value could be larger than the input value.
5. Coins of different color could be exchanged in one transaction. An output may bear more than one color using multiple OP_CHECKCOLORVERIFY (e.g. an 1 BTC output with color xxx and color yyy means 1 xxx coin and 1 yyy coin)
6. Using coins from other addresses, one may mint more colored coin than the coin he has. For example, with 10 BTC from address xxx and 1 BTC from address yyy, one may mint 11 yyy coins.
Backward compatibility:
For existing clients, the coloring information is just
and will be ignored
Possible extensions
1. To allow SPV verification of unique smart property (e.g. linking a colored coin with a real car), we need to ensure the uniqueness of the colored coin on the blockchain. A flag could be added to the minting and subsequent transactions to declare that only one UTXO may have this color at any time.
2. Sometimes you may want to restrict the total amount of a specific color coin in circulation. A flag could be added to the minting and subsequent transactions to declare that no more minting of the same color is allowed. (I'm not quite sure how this may work. Need more discussion)
These extensions require full nodes to keep an index for all colored coins in UTXO set
EDIT: These are not needed as there are better solutions: https://en.bitcoin.it/wiki/Smart_Property 
