In the original plans for The Godfather II, it was supposed to be Pete Clemenza who betrayed Michael Corleone for forgetting his roots back in New York. But the producers couldn’t reach an agreement with actor Richard Castellano, so they changed the story to Clemenza being dead and Frank Pentangeli became his successor and the betrayor.
In the original plans for Marvel Zombies, it was supposed to be Superman who broke through the interdimensional barrier and infected the Marvel superheroes with the zombie virus. But they couldn’t get permission to use a DC character so it became the Sentry instead.
In both cases, the original plan would have made a much stronger storyline than the eventual substitute that was used. Can anyone add some similar examples? It doesn’t have to be examples like this, where there had been actual plans to use a character that fell through. Any examples of how “this story would have been so much better if they had used so-and-so there instead of what they did” are welcome.