Halo's story is nothing to write home about.
Before you ask, I've played through Halo, Halo 2, and Halo 3. I didn't hate them, and I certainly don't think they were bad games. The praise of the story has always left me a bit confused, though.
Bungie has done some outstanding world-building, and I think that some people are confusing the world for the story. Sure, the Covenant are a fascinating alien culture, but the Covenant characters we get to interact with are either bland (the Arbiter) or comically stereotypical (the Prophets, the Brutes). Master Chief and Cortana get some well written banter, but the story is never successful in plumbing the depths of that relationship (even though Halo 3's plot requires us to accept that such a relationship exists). Avery Johnson could be replaced with a loaf of wheat bread, and I doubt anyone would notice.
Specific plot holes are not the problem here; I'm talking about a general lack of character development or growth. The story moves from plot point to plot point with mechanical efficiency, but never goes anywhere. Its best moments come early, while you are discovering the world, and it never manages to live up to the initial promise of its setting. There are too many fuzzy or poorly explained motivations for the story to hold up under scrutiny. Taking in the story of Halo is like drinking from a leaky cup. It only works if you don't take too long to think about it. To be fair, this works well enough through most of the games.
But a masterwork of storytelling it is not.