There is no genre that requires an all-encompassing story to be good or even great.
In the platformer genre there is Mario, no story, great game. But there is also Braid and depending on your taste you might like one or the other better.
In shooters there is Counter-Strike and there is Deus Ex, again great games, one doesn't even pretend to have a story, while the other has you undergo several changes, reinvent yourself as a character and make moral choices.
Same goes for all the other genres. What is a problem though is that some games pretend to have a deep story, but in the end they come out lacking. A good recent example of that is the singleplayer of BF3, it's fun but the story telling happens in cut scenes, gets you out of the flow and isn't really interesting. It's gets in the way of the mechanics and makes the game feel less rich instead of richer. (But then again, who plays BF3 for the singleplayer?)
A game can be good by having fun mechanics that are easy to learn and hard to master, visuals that fit the scene and are coherent (note that I don't say photorealistic or anything) sound and music to complement the experience and level design that draws you through the game and keeps giving you new and exciting ways to use and master the mechanics.
Now a story can add to this, a great story will keep you playing longer, have you feel more engaged and it makes the experience richer. Would the Mass Effect series be so much fun if we cut away all the storytelling? I don't think so, especially in ME1 the part where you actually play were a bit boring sometimes, but the story telling made the world come to life and made me invested in the success of the mission this made the game much better.
Storytelling is also a way to make the game more actual. One of the greatest examples of this is the GTA series, especially GTA IV was filled with story telling elements that have us look back at our society and the problems there in. Sometimes I just drove around looking at the world and listening to the talk shows on the radio, contemplating what was being told there. This experience is something mechanics alone can never deliver (although they can try and help)
However there is a dark side to this, some games forget that they are a game and try to be a movie or a book this can lead to problems since you don't feel like playing a game anymore since you have no impact on what happens. But even very story heavy games can achieve greatness, see Heavy-Rain as an example.
So to answer your question, no a great (open world) game doesn't need story at all.
It's a common complaint though in open-world games because story telling in open world games is quite hard since players do not follow a linear path. Games like GTA III~IV use tricks to make the game feel open but still have missions that are important to the story appear in a linear order thus giving both the sense of freedom as the above described pros of a story.
Btw if you are as interested in this kind of stuff as I am, I recommend you start watching the Extra Credits webcast, maybe start here? http://extra-credits.net/episodes/enriching-lives/