Maybe there should be more than one storyline with more than one character, and they merge into one grand story. That's a game concept more than it is a story, though.
How about a good prequel? A lot of time passed between Fallout 1 and 2 (50+ years), and a lot happened. If you will all recall, Fallout 2 took place north of the original. NCR was made up of lots of cities to the south, including the Hub and Junktown (I think). In any case, it could be the crusade of the founders of the NCR to build it.
If FO3 took place afterwards, most of the supermutants would be dead. After all, the supermutants are sterile and the game just wouldn't be much fun without them.
On the other hand, with all this crazy stuff happening in the Western U.S., what would be going on in Europe or anywhere else in the world? In a completely different setting, they could introduce other races. Of course, there would be ghouls (they're just irradiated humans).
Seeing the ruins of California is definitely a blast, but I'd also love to see what comes from the ruins of Europe. Do boat battles in the English Channel sound fun? It's narrow enough that trade could still go on, and pirates would surely take advantage of it.
How about Fallout: Generations? You start out with a plan of reuniting the remnants of civilization, a task that cannot be completed in one lifetime. You have kids and train them to succeed you. That really gets away from the idea of the game though, because you'd be controlling an empire, but it would still be fun.
I just love the Fallout universe and I'll play anything set in it. I wouldn't even object to a well-made first-person shooter (GASP!).
Bring back some memories, doesn't it, APTYP?