I would argue that you really need more than story. A trailer needs a couple things. So it needs to explain what the piece is about or explain the plot some. equally important it needs to have an attention getter or something to hold the viewers interest; this could be some funny dialogue, an interesting idea, a cool scene, action sequence, or plot revel. It needs to give the viewer a reason to care which might be fulfilled by the attention getter and maybe something to unify the above themes.
Sorry for this, but gonna rag on the FreeSpace Movie trailer to illustrate the point. That trailer was an intriguing idea in how it was put together, but honestly wasn't as good as it could have been. It did nothing to enlighten the viewer to what the game/media was about. If I hadn't played the games, I wouldn't have a clue what it was about. I asked my sister for her summary of what it was about and her response was "Well. . .there are some ships. . ..and they're doing. . ..stuff". That pretty much all I got out of it as well. The trailer also lacked a full scale attention getter. The music served very very well as a unifying theme and partly as an attention getter, but after about 50 seconds in I'd lost interest because nothing was happening and the song couldn't keep me occupied that long. What would have alleviated both major issues in my opinion was some sequences of actually flying and shooting and explosions and fighting the shivans after the 35-40 second mark. Alternate between the action sequence and the solemn view of the iceni moving and Bosch's solemn viewing of whatever and portray that as a reflection on the war. Have the flying and shooting sequences mute so that the only sound is still twinkle twinkle little star, and try and illustrate a struggle against the shivans where humanity clearly isn't winning to fir the dark tone of the music.
Now to bring this back to the relevance of Spidey's Awesome Trailer and the elements in it. ok what does this trailer tell us? Its about space ships and a war. humans are being attacked by evil looking ships and they are losing (i.e. all the stuff blowing up that isn't evil looking). the humans respond and put up a fight, but the outcome is uncertain though it looks slightly grimm with the deimos making a suicide run on the super big evil ship at the end. Now attention getter. that comes out right at the start as the tension is ratcheted up by the frantic sounding pilot as he freaks about about something. the shivans pop in, lots of cool explosions and dialogue that fits well with the scene. Basically Spidey's trailer hold the attention. now as a reason to care, there was an explenation at the start to "say freespace was a game in ...xxxxx""....dedicated modding community has worked on it since.. ...xxxxx".... and then you have the end with the "come see what you have been missing" bit encourage viewers to come visit the website.
tl;dr = spidey has an awesome trailer with all elements needed to make a good trailer
p.s. to the maker of the Freespace move trailer, sorry about picking apart your work and hating on it. I think It was actually really cool, and I know that I could not make a better trailer myself.