Writing, wit, and imagination. Fights and other tactical challenges. Dialogue and plot. Riddles and puzzles.
Believability is the single most important element, because it is what hooks the player.
The player must want to solve the problem posed by a particular scenario or she won't finish playing it. All of the elements of a scenario add to or detract from its believability and believability either arises or doesn't arise from all of the scenario's elements. For examples of believability, consider the naming of characters, towns, and monsters. The good designer will only choose names which make sense - which trip off the tongue. Frankly, some bit of gobbledygook or another is almost enough to make me quit playing a scenario.