Actually, he does have a point. Storytelling is just as much the techniques used to tell the story as much as the content of the story. Let's take F.E.A.R as a quick example. They used a few in-game cutscenes, but otherwise sticked with the player in control while the story was told.
To gain access to more storyline material, you could listen to voicemail and read e-mails.
Those are storytelling techniques, which may or may not be used in other games. Now let's take a look at Deus Ex. In the first Deus Ex, the story was told almost exclusively in the normal FPS view. To gain access to storyline information you could hack computers, read e-mails, talk to people and so on. For a fps rp game, it was quite revolutionary in storytelling techniques.
What he's saying, is that The Longest Journey - even though it had a wonderful story - had it's story presented in a way that other games had done many times before it. Hardly revolutionary in the way it was presented, neither gameplay nor storytelling wise.
However, I half-way agree with you. Storytelling isn't just about the techniques used. It's about the timing and writing as well. How the story unfolds depending on your choices and your exploration within a game.
So let's meet halfway on this. Storytelling is both about the techniques used and about the content itself. Okay?

This is exactly what I wanted to say, you found my words Deviate :) I might add something though, The Longest Journey - Dreamfall uses several playable characters storylines imbrication and this is quite interesting to see how they react from eachother actions. (I don't want to spoil so I'll not give any details.)
I'm not quite sure if I'm clear.

Yes, that's exactly what I had in mind.
Cause you're right again, it's +1 for you, though I don't know if it really matter that much :D

Story dictates gameplay.Gameplay does not dictate story. You do not get a story because you saw that scary house and investigated. The story was written so whatever happens in that scary house happens in that scary house. So when you come out of that house and say 'wow' it was the story, not you hitting 'W' to walk to the house and 'space' to pen the door to enter.

Yes, but there's gameplay, there's story, and there's way story is told. 3 different things.
Let's take The Longest Journey again.
Gameplay: Game is controlled using mouse, by clicking on items / NPCs. Gameplay is based on interacting with environment, items with each other, etc.. Gameplay is not focused on action, it's focused on using logic to get trough obstacles.
Story: Story is about woman named April Ryan ... ...
Storytelling: Story is told by interaction with NPC characters, by April herself, and by logs in her diary
Now, let's take your scary house.
Gameplay: Gameplay is action based, using keyboard and mouse as a means of controlling the game. Occasional puzzles may appear during the game. Game is viewed from first person perspective.
Story: Story is about little girl, who has lost in an old house and her brother, who came looking for her there. As he's trying to find his sister, he slowly uncovers true horrors of what happened there...
Storytelling: Storytelling is based on pure visual imput, no texts nor dialogues. Player needs to connect what he sees together if he wants to discover what happened there - noone will tell him. Occasional flashbacks in the history of house are used as well.

Lot of good stories on this list. Fallout series? Awesome. Deus Ex? No question.
I find it hard to believe that no one has mentioned System Shock 2 yet. I see Bioshock, which was really an homage to SS2, but you really have to play the original. Too many "whoa" and "WTF?" moments to list without spoilers, but it always seemed that although you could never quite seem catch up with any of the characters whose logs and e-mails you were reading, they had to be just around that next corner. It caused me many frantic searches for that next log to find out which way they went. By the end, if you collected everything, you had the complete stories of what happened to all these individual characters, and were figuring out how they all related to the main story.
And the series of messages that tell the story of Tommy and Rebecca are, when taken as a whole, one of the great tragic romances in gaming. And you never even see the characters on screen! Their last message is, I think, one of the most poignant moments I've ever seen in any game.
Great, now I have to go search GOG and see if they have SS2. Thanks a lot, guys... ;)

True, I'm ashamed I didn't notice noone wrote System Shock - the same applies to SS1 logs as well. And yeah, I was watching story of those two more eagerly than main plot of the game :D
Are you sure of that?
*spoiler*
I've got a feeling you met them ... Errrr ... Kinda ... The moment before they used escape pod, but I'm not exactly sure...
*/spoiler*

Most recently I thought Dead Space had a pretty interesting story, they have a prequel comic and animated movie. Very fleshed out if you ask me.

Speaking of animation and prequels. Anyone seen the F.E.A.R prequel? Freaky, freaky, freaky video... It came with the Director's Cut edition of the game.
Linky here

Well, I got a few games that I consider to have good storyline.
On PC:
- Thief series (Looking glass managed to create a believable world with this city).
- Myst series
- System Shock series (H-h-h-how could those ins-s-s-sects could f-f-f-forget my MAgnef-f-f-ficience!)
- Bioforge (just begging for a sequel)
On Console:
- Xenogears
- Metal Gear series
These are those I remember on the top of my head.
These

Circle of Blood
Betrayal at Krondor
Return to Krondor (the story was good but the gameplay was a bit "meh".)
Command and Conquer (i love the FMV parts)
Half-Life 1 and 2
Supreme Commander and Forged Alliance
Gun
Grand Theft Auto: Vice City
Daggerfall
Halo series (average when next to a PC FPS gameplay-wise but the story is a good sci-fi thread)
Baldurs Gate 1 and 2 (the Dark Alliance series was "meh".)
This Sims and Sims 2 and The Movies (ok that's a bit cheating because you can make your own stories:) ) Yup got it and loved every minute of it.

In case no one's mentioned it yet: No One Lives Forever. The first one, not the sequel.

Jade Empire and Beyond, Good & Evil.

I DOUBT anyone will share this example, but I loved Republic Commando. I liked the story a lot and the 3 other characters in my team felt like more than just AI to me. I just wish they would make a sequel to that story but I won't say way incase anyone who hasn't played it, might plan to. It's a fun game though with a good story... at least I thought so.

I've just started playing The Longest Journey and feel like contributing to the above argument. I would mostly agree with Deviate that it goes half-way. However I also think it also has some subtle aspects which begin to immerse the player in the role of the character in a way which is unique to video games. Small choices and the way that I think about the elements of the plot in terms of me instead of in terms of a random character are what drew me to artistic video games in the first place (Deus Ex being a superb example). Since there are so few games which manage to achieve this at all, I would put The Longest Journey in the good storytelling category.