As far as the "truth" languages are concerned, the ones I've heard of are Amazonian. These languages are constructed to keep very good track of what is and has happened; who owns or owned what (there is the famous "past for nouns", translated like "ex", so my ex-house for instance, but they also change the meaning so an ex-person is a corpse) and they keep track of what changes to what (that's the so-called "transformation morpheme" - since everything is constantly transforming in the amazons).~Marta
Also, there is something which is not only found in these languages, but in a lot of languages of the world, and is called evidentiality. Evidentiality means that when you report information, you have to mark it grammatically for the source. So, if you have witnessed something with your own eyes, you will use one construction, and if you have heard it, you will use a different marked construction. That helps keeping track of who said what and weather you can guarantee the information.
Such aspects when combined make the language more "explicit", and by that I mean, that it is difficult to be vague when speaking these languages. That's why all newer cultures appear as liars, because they do not specify enough when they speak. The "truth-telling" tribes can also lie, I'm sure, but probably not in the way of "omitting" the truth. For instance, imagine if I were showing you where I lived last semester, and I would say "This is my house"; well, these people would probably consider this a lie, because it actually "used to be my house", right? While we don't think it's such a big problem saying something like that.
Or even if I wanted you to think this is actually my house now, and then you found out it wasn't, I could say it was just a way of expression when I said "This is my house". I don't think the "truth-tellers" tolerate this. But the fact is that our languages are constructed in a way that there is much more room for manipulation, since it is not expected that you always give every detail about anything.
Lets just say these people are much more thorough when speaking.