In the first example (the story where...), 'story' is thought of as a place in which some events happened, and we want to talk about the events that happened in the story, not the story itself. That's what where does here: it ushers us into the story, (which is metaphorically thought of as a place,) to show us what goes on in there. That's why a where relative clause can be rephrased into an in which relative clause:
the house where I grew up => the house which I grew up in
the kind of story where you had to be there => the kind of story in which you had to be
But a that clause is normally a statement about a thing (itself, or something related to it), not what goes on in that thing (as a place):
The story that B told was not funny.
In the example above, B told the story itself. There's no suggestion as to what happened in the story.
That's the general rule about relative words where and that. However, there's an exception to that rule, and that's when the head noun (the noun described by the relative clause; e.g., man in the man that came) is place. A good explanation and many more examples can be found here. I'll cite a couple authorities on this matter too.
From A Student's Introduction to English Grammar by Huddleston and Pullum, p. 185 (adapted):
The non-wh construction is not always available when the relativised element is
adjunct (or complement) of place; the example a place (that) you can relax, with the head noun place, is perfectly acceptable, but in sentences with head nouns less likely to suggest location, a wh relative would normally be required. That is, we would say This is the web page where the claim was first made, not *This is the web page the claim was first made.
From The Cambridge Grammar of the English Language by Rodney Huddleston and Geoffrey K. Pullum, p. 1053 (adapted):
Relatives introduced by when† ... have non-wh counterparts, with or without that:
- i I haven't seen them since the day [when/(that) Kim was born].
Relatives introduced by where, by contrast, do not in general alternate with the non-wh type except where the antecedent is a very general noun such as place:
- i This is much better than the hotel [where we stayed last year]
- ii This is much better than the place [where/(?that) we stayed last year]
The (?) annotation in [ii] applies to the version with that (?the place that we stayed last year); the bare relative (the place we stayed last year) is more acceptable.
The restriction to wh relatives does not apply when where is complement to stranded at: the hotel where/(that) we stayed at last year. Where ... at seems to be a blend between where and which ... at; note that with in we can have which but not where: the hotel which/*where we stayed in last year.
Are there any nouns besides place that have this quality? I don't know, but the citations above don't seem to assert that there aren't.
† I guess partly due to the fact that you don't usually think of things as periods of time: *the story when you had to be there, so the problem doesn't arise in the first place.