So, Deus Ex had a wonderful story and world, but you could have changed a lot of the items and themes around and still gotten the core gameplay: explore a place, solve puzzles, shoot enemies, navigate areas stealthily. The fact that it had a really solid story behind it and lots of fluff was icing on top--had the gameplay (the combination of movements, game rules, and objectives) been lackluster, you would've stopped playing (probably).
Compare this with games like Tetris, Mario, or even Starcraft: there are people that will wank on and on about how great the stories are, how rich the worlds are, how awesome the symbolism is--but the core act of playing the game is what makes them last for so long.
From the FPS genre, we see that Half-Life and its sequels had pretty flimsy stories (despite being regarded for having such great cinematic experiences for the time); however, their use of tight, solid gameplay (both in combat and in puzzles) are why they're loved so much today. Indeed, the better storytelling in Portal 2 was greatly offset by the more-restrictive gameplay it had compared to its predecessor: Portal was much more free-form in portal placement, and did less to hint what the obvious move was.
Bioshock Infinite was a masterpiece of storytelling, and had a genuinely thought-provoking ending and plot. Yet, the actual gameplay was not crazy far ahead of what we've seen in its contemporaries, and that's why it's probably not going to go down as one of the classics of gaming for this era.
~
The big problem with emphasizing story and narrative over gameplay is that it is very easy and seductive to write a rich game world with lots of symbolism and all the rest--but it's hard to see when you're not good at it, and you end up creating kitsch intellectual garbage. Gameplay, though, is easy to test, harder to create, and is what actually ends up immersing your audience and bringing them into your game.