How can I get better at lying?
Having not played this game, or played in the group you're playing, I can't give specifics, but I can talk a bit about my experiences with subterfuge in other contexts.  (poker is a classic for this)

The first, most important thing is that you need to have a story in mind that you want the other person to believe.  Simply saying no when you would normally say yes is an easy discontinuity to ferret out, especially when some of your other in-game behaviour doesn't match.  Check out some poker commentary; every now and then, they can tell almost exactly what the player is trying to represent, even though the cards are different.  If poker is too boring, check out stabby's team fortress 2 videos.  He also mentions what he meant for his targets to believe.

Try to keep track of what your recent visible actions have been.  If the story you'd like your targets to believe doesn't make any sense together with your history, it won't work.  Try to account for the other player's perspective.  Any knowledge helps.  In poker, if you're trying to represent an ace, you need to make sure your opponent doesn't have one already.

If your target has incentive to believe your story, it makes it easier.  Give them an angle for possibly double-crossing you.  Make them believe you are too far behind everyone and feel like being king-maker.  Give them a clear benefit in the deal with a small, obvious way that you 'plan' to take advantage, so they can think they're ready to defend.

One important thing, as has already been mentioned, is to not lie most of the time.  If the culture that you a playing in is about always being cut-throat, then you need to shake that up.  Give a few games away, act on impulse or emotion for a little while, but most importantly do this in such a way that it looks&amp;sounds like your lies.  As a kid playing memory tile games, I'd often point out the correct tiles for the others and they'd think I was lying and go for something else.  You might have to be careful with this.  If you mess with the social contract too much, the game becomes frustrating for other players to the point they may decide they don't like playing with you.

Lastly, pay attention to the pace of the game.  If you make most of your decisions quickly or even flippantly, you need to match that speed with your lies.  The bonus with that is that the faster things are going, the smaller the misdirection has to be.  If the game is usually a slow, thoughtful process, you'll have to think through all of the details of your story before putting it out there for others.  In any case you need to be a lot quicker with your thought process when lying than during normal game-play, so it can often be helpful to slow down the game, think through a story, then discard the story and give the truth.

I hope that's helpful.