If we use colored coins and atomic coin swapping to clear transactions on-blockchain, there are no need for brokers. We still need trust, not for brokers, but for gateways which will take fiat and give IOUs in form of colored coins. We trust them that they will convert IOUs back to fiat on demand. So actually we will trade not USD/BTC but MtGox USD/BTC, BTC-e EUR/BTC, etc. Even MtGox USD/MegaExchange USD.
If you placed order, you should not be able to not fulfill it (until you cancel it). Maybe we can devise coloring scheme that can be used to achieve that with help of
contracts in trust-less way.
Voluntary rating of the brokers from the clients could be used to indicate the trustworthiness of each broker.
Doubt it will work - too much possibilities for manipulation.