Final Fantasy XI had a functional auto translate function. You had to type out the first 3 letters of the word or phrase you wanted, hit tab, and it would give you a list of words or phrases to pick from (the game had a big list of ordinary and game related vocabulary built in to the translator). You would pick a word, and it would appear in brackets on your screen, and translated for the other people. The communication was rough but doable. It came out like this: [Gather together][casting spell][Valor Minuet].
Of course some people just HAD to have fun with it though, like:
[Mithra] [Hand] [Job] 5 gil
LOL
At any rate this system made it possible for people to coordinate parties with people that spoke in any language. For a game like this, a similar system is definately doable.