I guess its kinda like pr0n

Some like a good story, others are just in it for the fun
But just like pr0n is of the "entertainment" industry, so too are feature films. Some are subtitled, some are arthouse - and all too many are holywood schlock But I go see films of all sorts - I just alter my expectations to suit the material, and I'm almost always happy!
If I was a multi-player shooter, story is of no consequence. If it's an RPG - then the story is an absolute must. I'm really enjoying EVE-online, but the story there is (at the moment) of no consequence. I don't care for the back story - I just want to make some cash, to buy bigger ships!
For me it's not so much what the story is - it's how it's implemented, and if it has any real relevance to what's going on. RPG's are fundamentally about telling the story - so yeah, it's important. FPS's are about not dying, and landing headshots - so no, the story isn't really important...
But as Major C said, the COD4 single player story is utterly brilliant, and really (really!) draws you in! It creates a sense of importance and urgency that you just can't achieve without a solid and compelling story. Sure it doesn't carry over to the multi-player side - but that's about headshots and knifing!