I voted for story. To me the storyline must be fully developed with characters who are more than cardboard cutouts. As the creator of Final Fantasy VII said, he "tells stories first."
You could easily say "if the gameplay is good enough you can forget about the story or lack of." I nitpick. I like a storyline, even a simple one such as Doom 3 will do. All I'm gonna mention is one game: Devil May Cry 2. The storyline was completley out of the woodwork, and the gameplay was very repetitve. I'll only really look for a story in non-FPS games though. (Painkiller...)
I think soundtrack is second though, my favourite OST is Final Fantasy VIII. Very emotional, artistic and with a wide range of styles. Also, i believe that unlike a lot of game soundtracks, it stands up on it's own as a good album. When used correctly, a soundtrack in a game, film or television programme can merge totally with other elements and elevate it beyond anything it was before. That's why i don't really like ambient soundtracks such as Parasite Eve 2.