First problem: the guessing game
In some cases, dialogue trees can be really complex (indeed, more conditional graphs than trees) and exploring them becomes a real puzzle, see e.g. Galatea by Emily Short.
In other cases, as in Deus Ex: Human Revolution, you can see some trappings of a dialog-specific gameplay. But it is still largely a mix of skill checks and guess-the-right-answer with a magnificent paint job.
What you lack in all those cases is simple: the ability to plan. To take the lead, to act rather than react, and make decisions not for their immediate reward, but in preparation for other options later on. A rule system that allows you to learn patterns and evaluate what the effect of your choice will be, not just vaguely infer it from situaton-specific hints put in by the writers.
In the very best case, you approximate this by replaying the same conversation again and again until you get the gist of it, but that's level memorization, not skill acquisition.
(Disclaimer: this is something our own contest entry Exeunt Omnes was entirely guilty of, for lack of time. I am not proud.)
These games are more akin to puzzles in a point'n'click adventure than to battle systems, or strategy and simulation games. Which is fine, but not quite what we are looking for here.
Other examples: the insult swordfighting in Monkey Island, any conversation in Interactive Fiction, the Phoenix Wright series and the entertaining Socrates Jones: Pro Philosopher, or Goblin Noir (despite its appearance of having a battle system, the battles are really puzzles).