I actually think the one think that can't be changed in AOTC is Hayden & Natalie. To me, they just weren't perfect for the part. Harrison Ford, Carrie Fisher, and Mark Hammill, not academy award winners, are perfect for their role. You can always say to yourself that I couldn't envision anyone else playing that role. For the prequels, Liam Neeson was perfect for his role, and so was Ewan McGregor. Throughout Episode II & III I always thought there was a better couple to play Anakin & Padme.
To me the biggest reason why I think people don't like AOTC is the love story. True, there is some cringeworthy dialogue, but I just don't think people want to watch a Star Wars movies with the love story as the central point. In the ESB & ROTJ, the romance between Leia & Han was minor subplot that didn't interfere with the movie. I know so many people who were so turned off from AOTC when they saw it in the theater. They would shake their heads everytime you mention the love story.
As I said, I actually like AOTC, I dont think it is a great Star Wars movie, but I can still watch any Star Wars movie all the time. Lucas made a bold move with the prequels:
TPM: The Setup
AOTC: The Romance
ROTJ: The payoff
Most people just wanted the payoff.