For a piece of normal static fiction, be it a novel or a film, a basic prerequisite for success is for it to allow suspension of disbelief. It shouldn't have too ridiculous a plot, everything should work either as it does in the real world or according to some coherent fantasy-world alternate reality, and the characters should act like real people. Now this is something which authors spend a lot of time making sure of, but compared to the situation in the interactive arts1 their work is a doddle.
Consider. In a novel, how do you make a side character - someone other than the protagonist - seem real? Well, you give them lines and mannerisms that form a coherent whole, such that they seem to have a definite character the reader can "get to know". Now consider the equivalent problem in interactive fiction. We have a character other than the protagonist - what is conventionally called a non-player character (NPC) - and we want to make them seem real. Now the problem is that the player can interact with this character in many various ways. Suddenly all the things that in static fiction you can assume, like that the character can see the world around them and can think for themselves, can easily become suspect. Because, given that no artificial entity yet can, our character can't think for itself.
But the point is we don't actually need AI to solve the problem. People are willing to believe a character is real, unless it does something to give away that it is not. This is what is known as the Eliza effect - the assumption of a far greater intelligence behind something that is pretending to be intelligent than is actually warranted. So the main challenge is to not break the suspension of disbelief, rather than to actively create one. It is there by default, and can be strengthened through good use of language, but can be utterly destroyed by bad programming.
So, given the fact that intelligence is beyond our grasp, how do we create a character which the player can believe to be real - a believable agent? The Oz Project (http://www-2.cs.cmu.edu/afs/cs.cmu.edu/ project/oz/web/), one of the main groups who researched in this field, suggested the use of "broad but shallow" agents2. Broad in the sense that they are able to operate believably in a wide range of situations, but shallow in that they won't necessarily work well if pressed on any one area. So although they will respond OK to you trying to kiss them, attack them, or send them to the post-office, they probably won't be able to carry a decent discussion about the economic effects of off-coast fishing on New Zealand. Unless it's really relevant to the story. So although of course a persistent player could always unearth the stupidity at their dumb core, in the normal running of the story they should act as if they knew what they were doing.
Given that we need only a crappy approximation of AI to achieve this, then, it really shouldn't be too hard. And in fact the Oz Project developed some pretty decent characters, including a very life-like cat called Lyotard (humans are much harder, because understanding language is a huge problem). As far as I know the actual programmes are lost, but some transcripts of them in action, along with detailed explanations of their architecture, can still be found on the site. See reactive agent planning for an example of the low level of "AI" that this needs. See also Galatea for a more recent work of interactive fiction which adventurously tries to make a very human, and very conversational, believable agent.
1 By "the interactive arts", I'm referring rather loosely to any form of interactive fiction, and not just the one that node is about. Basically, fiction which the reader has the ability to influence, generally by directing the actions of a character.
2 So this is the exact opposite of that advocated by pure AI researchers like Douglas Hofstadter, who think that we should study very specific narrow microdomains in great depth so that we can understand the basics of what makes intelligence. They are probably right, if the aim is actual AI, rather than just a believable agent.