I personally believe the e-gold guys were working in good faith to produce an alternate currency, one that functioned like cash, but that was backed by actual gold. However, it is generally agreed that the majority (or at least a significant portion) of the business transacted with e-gold was illegal in nature, and much like cash, once you spend your e-gold, you can't call up the e-gold company and tell them to reverse the transaction. you have to get the other party to return the money, and much like cash transactions in the real world, that can be quite difficult. In fact, the anonymous and electronic nature of e-gold made it better suited for many criminal activities (especially fraud) than cash, as the fraudster never had to actually meet his mark.

Obviously, all this caused a lot of complaints. Add in the fact that the anonymous nature of E-gold meant that most people weren't paying taxes on the transactions in question, and the government was going to step in and shut them down.

Now, I'm no lawyer, but I'd bet that if you set up something like e-gold tomorrow and made it non-anonymous, that, by itself, would make the thing largely acceptable. You would probably need to set yourself up as a bank or something, and you would probably need to set up something to make it easier for your customers to figure the taxes they owe, (and for the IRS to figure the taxes they owe) but I think the big barrier was anonymity.

As a secondary step, some sort of dispute resolution protocol like paypal has would probably also help, but I believe that is secondary to the first concern.