A role-playing game is one where you play a different role than You. This requires a few things:
1: You get to choose who your character is, what its motivations are, what it looks like, etc.
Failure: Final Fantasy, Chrono Trigger, Thief, System Shock, GTA
Marginal: World of Warcraft, Morrowind
Success: City of Heroes, Spore, Dwarf Fortress
2: You have the character interact with the world in a meaningful way. Ideally, the game should not restrict you from doing something that is within your character's legitimate power.
Failure: Final Fantasy, World of Warcraft, Chrono Trigger, City of Heroes, Thief, GTA
Marginal: Morrowind, Spore, System Shock
Success: Dwarf Fortress
3: If the game has a plot, you should be able to have any effect on that plot that you want. If it doesn't, you should be able to create your own plot and change lots of things about the world.
Failure: Thief, WoW, Final Fantasy, Morrowind, City of Heroes, System Shock, GTA
Marginal: Spore, Chrono Trigger, Dwarf Fortress (future dev)
Success:
4: Your character should persist from one game session to the next, growing in capability. This might include equipment, social influence, money, skills, etc.
Most games we consider to be "RPG" succeed at this. Donkey Kong does not, and so cannot be called an RPG.
Based on these criteria, different games get different things right. None of them get it all right. However, we're looking simply at computer games. When you talk about roleplaying games on the table, with pen and paper and dice, it opens up quite a bit. This is because your character's actions are limited only by the imaginations of the people at the table. It will be a long time before computer games offer that variety.
So what are these games, if not role-playing games?
I argue they are largely Story Completion Games. The story is already coded into the game, and you can make small decisions along the way, and you can direct the game to different possible endings, but you cannot create your own ending by taking actions the programmer didn't anticipate.
You might worry that this places a burden on RPGs that cannot be fulfilled. I'd say it's a misconception that a computer game can even BE an RPG. We assume it to be so because we see so many games labeled "RPG" but the genre started out with roots in wargaming and supported by the most powerful computers on Earth: the brains of the players.
I say you cannot expect a computer game to be an RPG for the same reason you cannot expect a cat to play the fiddle. The song is just too difficult to play for something of such limited capacity. The cat can't even hold the thing right.
To take the analogy a step further, an FPS computer game was made for computers. Nothing of the sort existed in the way strategy games and card games existed before computers. The FPS genre is like making an instrument just for cats, that they know how to play, and so the result is as pleasing as you can expect.
Computers can run computer games. But computers cannot run role-playing games. Not yet anyway.
EDIT: I'm leaving rules-less MUDs out of the above description, because they're really just a form of telecommuting to your game instead of showing up with chips and mountain dew. They're less games than chat systems.