I am picturing a fun session where the players and natives end up using gestures, body language, sounds, magical effects, and/or drawing in the sand or on rocks, to try to communicate.
I might handle this with a simple Intelligence roll to successfully transmit a message to the natives and to successfully receive a response back.
Apply some kind of success/failure table to the result. For example:
20+ = message is interpreted perfectly
16-19 = Message is mostly understood, with some minor component missing
11-15 = Message is somewhat understood but also somewhat vague
6-10 = Message is extremely vague with some definite misinterpretation
<5 = message is interpreted opposite of intent (or interpreted as a threat, insult, whatever)
Bust out those improv skills - you are going to need them if any roll is less than perfect!