Games don't need stories.

[onikenshi]

Games can have little to no story and be considered the second coming. Look at NSMBW and MW2. But then you can have games have a good or great story and be engaging such as MGS4, Zelda, GOW1,2, Gears of War 1,2, etc.
Story may not be necessary for some genres but for alot it can be something important and/or special. JRPG's/WRPG's obviously, but then you can also look at platforming types like ratchet and clank, Kid Chameleon, FPS's like KZ2 and Haze (story was actually very interesting, but gameplay and enemy AI was.....you fill in the blank) along with Halo, Red Faction 1 and 2, then you look at action adventure types like SOTN, fighting games like KoF series (Orochi and Nest sagas for example), Fatal Fury, SF, Guilty Gear (this one had an extensive story behind each character), and even combat driving games like Twisted Metal had some good story behind several characters.