Well I finally got around to completing Fable II last night. I must say that despite its many, many, many technical and gameplay faults, the story was one of the most intriguing game stories I have played through for a very long time.
The entire tone of the storytelling was very mature and professional, for lack of better words. I think it was because it didn't play around. It was honest and blunt with the player in a way that most games fail to be. A simple example is you have sex. You don't have 'hot coffee' or a 'chat'... you have sex. Similarly, key story events just happen the way they do in any good adventure novel or movie.
Perhaps the story of Fable II is not trying to be a game-story, but just a story. There are plenty of more-compelling stories out there; when you look at the plot of Fable II, it is really quite simple. Look at Fallout 3: the sole reason it has taken me so long to complete Fable II. The story was, for me, far more interesting, but that said, it was still very much a computer game story--a story that knew it was a computer game and was careful not to be anything more than that. Fable II, on the other hand didn't sell itself so short to fall into good guy/bad guy blue blip/red blip divisions. The decision making aspects, the just-living aspects of it, the entire game embraced themes of just being... human. There are no good decisions and bad decisions, just favourable and unfavourable consequences.
[slight spoiler in this paragraph]
The story was certainly loose in parts and non-existent in others. How you actually defeated Lucien is never really explained beyond "It's your destiny." But no game before this has made me feel so responsible for my character's decisions nor has a game before this made me feel so affected by the consequences of those decisions.
Perhaps that is it: the sheer intimacy you develop with your personal character draws you, the player, further in Albion than a typical game world and thus ingrains the experience of the story that much deeper.