The other alternative for exchanges outside of a government body would be self-regulation. If an exchange participates in a self-regulation organization and follows a set of established best practices, the exchange would get a stamp of approval to publicize to customers and improve credibility. Over time, exchanges that participate would most likely gain share faster than ones that did not abide by the exchange industry's best practices in security, third-party auditing, claims handling, etc.
Im not discussing which system is best. I personally distrust any regulated system. But in the eyes of a lot of people a regulated exchange has more credibility.
Separately, while there is a lot of animosity in the BTC community regarding the US financial system, the FDIC and SIPC seem to be good ideas that may make sense to implement for exchanges and other eWallet providers that hold customer funds. These organizations provide insurance in the event of bankruptcy of a deposit-holding company, reimbursing customer for their lost funds up to a certain amount. This might also give newbies more faith in the system.
The FDIC and SIPC are horrible ideas because protects reckless business. The exchanges doing it voluntarely would be a different issue since they would have the incentive to police each other to avoid someone abusing, because they would have to pay for it.