One idea that popped into my mind over my cornflakes is...remember when the Clone Wars were first mentioned in ANH?
It was a lovely little throwaway line which expanded the canvas of the story back and gave the saga more depth, the prequels don't have much of that, a few more lines (perhaps by alien senators or Jedi which could be added via subtitles as in the MagnoliaFan edits) could flesh out the Sith/Jedi conflict or the Naboo/Trade Federation dispute.
And it's Clone Wars isn't it? Not The Clone War.
The Naboo crisis doesn't involve the Clonetroopers (officially they hadn't been invented yet) it might be fun if the Gungans/Naboo were helped by a mysterious uninvited, shadowy third party, a reveal in Episode 2 could expose the secret that the Clonetrooper concept was being tested even back then ( a small team lead by Fett could be aiding the Naboo from behind the scenes with their knowledge... they do seem to get into that palace a little too easy for my liking).
The order for the production of the Clone army came around the same time as Naboo crisis so it would make sense that Sidious would want to test both sets of his troops for the more major seperatist war and the rise of the Empire.
The added mystery would counter some of the silly antics of the Gungans (even after the worst of them have been trimmed out).