How about the idea of making the Niemodians slave traders? I always like the idea that the galactic dispute is over slavery, hence the Niemodians' obvious evil motives.
Also, I think the beginning of the movie needs to happen much faster. It's too slow as is. What about starting the movie right off with the invasion of Naboo?