"Harder than [you] think"? Oh, I certainly believe that storytelling in an open world is indeed difficult, if not impossible, to properly pull off. That indeed was a very, very good article- very relevant, and it pretty much underscored the factors that make video games such a rather difficult medium for story and action integration.
Perhaps the big thing that I took away from the article, at least with regards to a solution, is that to mesh a narrative with the player's actions would essentially require a dynamic, maybe even procedural, story itself. Pretty much like "multiple endings" but taken to the nth degree. The article talked about the author's playthrough of Uncharted 2, where his character killed about 800 people- imagine if that were actually worked into the story itself. Your character is no longer a "likable treasure-hunting rogue", but a feared and murderous warlord. I have no idea how such a solution could be reached with modern technologies and paradigms, but the integration of "player-story" and "intended story" makes for a compelling, if vexing, conundrum.