Good thread...and thought about this before. I think sort of along the same line as others have said. They could have kept many of the same core ideas, but just made it much, much more watchable and credible.
The character of Shinzon was a good idea, but he should have just been Romulan -- scrap the entire Reman thing. And don't make him a clone of Picard...just make him an intellectual equal to Picard.
Those two choices didn't really contribute to anything positive for NEM. Neither was believable and the problems just flowed from there. Like the Klingons in TOS, the Romulans were the primary enemy in TNG...they were the main poltical/military rival of the Feds from TNG's very beginning. It would have made perfect sense for them to connect the events from "The Neutral Zone" to a final movie involving a Romulan conflict. As it was, the Reman (and clone) story-lines were too convoluted and far-fetched (even by Trek standards)...it wasn't believable and it just wasn't necessary.
I always thought it would have been cool to see a Romulan Julius Caesar....a calculating, ambitious, brilliant political leader (praetor) that became so popular the Senate and the people granted him dictatorial powers over the government and military. "Shinzon" could have been his title (ala Caesar, Kaiser, etc.) but not his actual name. And he wouldn't have to be pure evil -- just a power-driven guy who wants to advance the future of the Romulan Empire...just like Picard and everyone in Starfleet wants to advance the future of the Federation.
No need to destroy Earth (again)...just a really dynamic, powerful, and persuasive villain who instigates a conflict over something important (resources, imperial expansion, etc) and represents a long term threat to the Federation's interests.
It would have been easy too --- just set it after FC and the Dominion War when the all the great powers are either obliterated (Cardassians), or severely weakened (Klingons, Feds).
In fact, it would have been great (imho) if they would have just never done INS and extended a seriously re-tooled NEM storyline into a 2 movies....in which Movie IX was an Empire Strikes Back sort of film (the villain wins and leaves us wanting more) and Movie X be the final victorious mission of the TNG crew, in which they defeated a great villain and secured the Fed's future for a long time.
I was dissapointed in NEM (and INS) b/c I enjoyed TNG so much. They deserved a more epic and enduring swan song. But...it is what it is...