Not only are there bits of pointers hanging around to quests that can't be finished, but there are lots of quests that you have to do in a certain order to reap maximum advantage. This is very foolish in a world in which you can wander randomly. If you go into building B before building A, you lose the opportunity to be rewarded by someone in building A for rescuing the person in building B, and they don't recognize your achievement retroactively.
Similarly, there are lots of quests where you don't know what the triggers are until you talk to the questgiver, and if you don't have the random item they're looking for, they won't offer the quest again, or they attack you, or disappear never to be seen again. This makes for a particularly annoying brand of save-and-reload gaming.
You said it. This is the sort of thing that really turns people off "open" style RPGs and encourages linear gameplay. And I can't say I blame them.
FO2 is really bad for it, perhaps moreso than other RPGS; for an open-style game, you really have to do very specific things in very specific orders to complete quests to their fullest.
I recently started the game again, and while it's enjoyable, it's a constant game of "guess what the devs are thinking/want me to do" more than a real RPG.
Pretty off-putting when it comes down to it.