Nice, does that apply to all Halo soundtracks? Because I believe only the first Halo had that iconic menu music.
Ahhh, that's the catch: the webpage doesn't say. But I think, since they specify the Halo 3 OST and not just "Halo music," it only applies to that specific soundtrack. However, you could either use a similarly iconic song (like H3's "Finish the Fight"), find a particular segment of one of the H3OST's songs that greatly resembles the original theme and loop it, or obtain a music license (good luck with that: they can be real expensive, something i'm not sure you'll want to do for something with a $0 profit margin).
Another option is to just go ahead and use the song: best case scenario, they don't notice; worst case scenario, you get your @$$ sued; middle ground: they ask that you remove the song from future downloads. Ultimately, though, I wouldn't worry too much about it; when people unlicensed music in Machinima (and, believe me, a lot of them do), properly crediting the artist is usually enough to keep the lawsuits at bay. It's a risk I leave up to you.
My advice would be to take one of my earlier suggestions, since they're safe and would provide all the fanboys with some real Halo music. However, I have downloaded a mod that uses Motorhead's "The Game", and I'm not sure whether it's licensed or not.