And by story do you mean the main storyline or any sort of storyline? In games like Fallout: NV or Oblivion, most of the fun is invested in the side quests you take on. Without good writing, relatable or intriguing characters, and investing plot elements though, they all inevitably devolve into some sort of Kill/Fetch "X" amounts of subject "Y" for "Z" Sword of +5 "Specific Attribute" affair. What really brings games like Saints Row 2 alive isn't the random cops and robbers BS that my game turns into whenever I co-op (though it is really good dumb fun), it's how much of an enjoyable asshole my player character is and how well he's portrayed as an enjoyable asshole in the cut scenes, in-game dialogue, and mission objectives. Those missions where you kill Maero's girlfriend, Shogo Akuji, and Mr. Sunshine make my wish fulfillment power fantasies all the sweeter.
As fun as a well designed sandbox game world is, without any structure to the fun all you're left is a fleeting kind of enjoyment that won't have any lasting impact on you and will probably end with you making your character climbing to the top of the tallest thing in the game map and jumping off.
Edit: What really brings the main storylines of those games to life for me is trying to work the choices I've made in the side missions into some sort of evolving character ark that effects my overall decisions in the main plot. A standard hack-and-slash RPG plot is fine (Morrowind > Oblivion), but a character with a well versed back story doing those main quests is better.