One possible solution would be to simply make any transaction with an output value less than the minimum fee non-standard, so that those transactions won't be relayed or mined by miners. After all, if the value is less than the minimum fee, there isn't any rational reason to spend the output. (the fee is zero with sufficient priority mind you, but zero-fee tx's probably won't get mined forever)
A very good idea! I hope this gets implemented and used by the major mining pools.
Well then that would stop/damage the use/development of 'coloured coins'.