Sadly that's an issue that's endemic of RPGs in general.It's interesting to note that, since a skill check is required in order to lie convincingly, you can sort of tell whether an NPC is lying by whether or not the GM is making that NPC roll a skill check.
Most players get very nervous when the GM rolls dice, or asks the players what a certain trait on their character sheet is.
Donovan has a good point here. Perhaps the issue is that the familiar method of antagonistical GM'ing is is not appropriate for this rpg. Not everything should be an opposed roll.
If the GM wants one of their characters to be lying they don't have to roll for it. If the players think someone is lying, maybe they, the players, should choose what to roll depending on the situation. Perception to see if the NPC is sweating (maybe even requiring a lore check to know what the species equivalent of stress sweating is).
If the 'lie' is about something the player knows about, the player can direct the encounter by saying "this used ship salesman is trying to pull a fast one, I'm going to roll mechanics to catch him in a lie".
This also brings to point one of the mechanics of this system. Whatever the skill used, a player could use a triumph to say a ln NPC is lying even if they aren't. Now GM could say no to that, but a good GM (especially for a player empowering system like this) should be able to go with that.