Today I had the same problem.
I remove transactions.nxt and blocks.nxt from the nxt folder and nxt started successfully.

I have no reason to doubt that colored coins functionality will be released, possibly with some delay, but we do need client support for it. I think pastet89's problem is that he doesn't fully understand the implications of colored coins (Asset Exchange). It is similar to ripple. ripple allows anybody to issue any three letter "currency", like USD, BTC, even DOG. All anybody has to do is send some to somebody else to issue it. There are no checks and balances at all. Anybody can send anybody a billion USD or a billion BTC or a billion DOG.
What does it mean to get something in ripple? It is all dependent on the issuer. This is why there are trust lines and the restrictions on receiving something you don't trust. It is expected that gateways will issue USD only for validated USD deposits and in turn, when the ripple USD from that issue is redeemed that the fiat USD will be sent to associated bank acct.
"ALL" that the Asset Exchange does is implement functionality similar to the above with the restriction that only a single account can issue each specific asset. So, we will get USD, BTC and probably even DOG Assets in NXT. Whoever the lucky one is that gets the BTC asset will be able to sell the BTC for NXT. I also imagine that if you return the BTC asset to that acct, a corresponding amount of BTC should be sent to your bitcoin address. At what redemption price? That depends totally on the issuer. At what fees? That depends totally on the issuer.
It is his responsibility to do all the real world interfacing. The moment there is an unissued BTC asset for a bitcoin deposit or a bitcoin transfer that is not made for a valid BTC redemption, the trust in the BTC asset owner will drop and soon nobody will use it.
This is the same problem that ripple gateways have. I have said this weeks ago. just because we get Asset Exchange, it does NOT solve the lack of reliable NXT exchanges. This is why I have put in the efforts to get NXT trading inside ripple. Asset Exchange is cool, but the entire process of getting recognizable assets and trusted issuers is not going to be as fast as people here are assuming. Short of CfB getting the BTC asset and deciding to spend his time doing BTC/NXT gateway, the community will have to develop the trust for the lucky winner of BTC asset.
My prediction is that what we will have is half a dozen people who end up with a decent combination of trustworthiness and asset name and inclination to do BTC gateway. This will fragment the market for BTC/NXT and it probably will stay this way for a while.
NXT software cannot magically enforce gateway behavior. If you expect this, then how to explain the turtles idea. NXT server uses star trek transporter tech and beams turtles to desired location on redemption of turtle coins? Nope, that's not till NRS version 6.6.6
Asset Exhange requires trusted issuers to do the gateway function.

Everyone should Vote here:

https://bt.irlbtc.com/view/417125.0

NXT is on top - DO IT!

Asset exchange = colored coin tech. If you understand how colored coin works, you will understand asset exchange. You can read my first draft paper to understand how generally it is supposed to work.

Link, please.

It would attract new users