This sounds like a very good idea and I would happy pay a few bucks for it on Android the next time I have to travel somewhere I don't speak the language.

Have you considered providing the flip side of the conversation? I would want to use an English interface to present a question and possible answers to a person who speaks another language, but it might also be possible that I'd want to let them pick from a list of phrases/questions in their language and allow me to answer as well.