Personally, I think it has an awesome story.
It goes deep into backstory, and a lot of things tie into each other.
All spartans are fleshed out well, contrary to what most will say; John-117 is by no means a faceless, fearless space marine. He appears to be because of portrayal in the games. He does not speak much, and is faceless in them. To those that play the games a little bit, this is fine. He is 'them'. To those that delve into the universe, though, he gets his face, and personality.
'Playing Halo' barely touches the games' stories; do you read every little bit of the terminals, think about everything said, and crossreference it to itself?
Do you tie it in to the various books, graphic novels, and Legends?
At the beginning of the Reach trailer, Emile(I believe, forget specifics of it right now) referenced Pegasi, and how he didn't think anyone survived. Pegasi had a major battle where 300+ Spartan IIIs were massacred even before it began. Part of one of the books.
If anyone that says it has a 'bad' story knows who the Precursors are, then I will be surprised. And not the Forerunners, Precursors.