[Quiet Man Cometh]

I agree with Sheol's first point but will rephrase with the idea that any genre story (sci fi, fantasy, what have you) should be linked to the genre enough that if you take them away, the story is changed. One snag I seem some people having with Fantasy (haven't read enough sci-fi to say on its part) is that they use it soley for "appearances" sake and if you were to set the story in the real world, or another genre, it wouldn't change. That basically means the genre didn't matter to the story.

One thing I think people care about when it comes to sci-fi is the science part. Just having aliens doesn't really work, since they aren't necessarily science on their own. Think of how important technology is to Star Trek. One of the points is that it's the technological advances that allowed mankind to explore space to begin with. Then there's all the alien stuff they come across and the usual "how much it too much/how far is too far" question.