Good thread, MrInsaneA. AOTC always was the most broken of the prequels to me. It has a lot of interesting ideas, but the whole thing is just executed horribly. I spent a lot of time thinking about how to fix AOTC as well
My main idea is this: the Republic has ordered the creation of the army. The reason Amidala returns to Coruscant is to vote on whether or not to deploy the army. This set up can be conveyed in the opening crawl. By making the characters aware of the army, it removes the nonsensical 'mystery', as well as all subsequent plot holes from the story, but will also make them seem less dumb.
Obi-Wan's little detective story can be changed, leading him to Geonosis instead of Kamino. It will also allow for the removal of Jango Fett (by turning him into Boba in a less integral part or removing him completely), Dexter's Diner, and the obvious scene with the younglings.
This will free up more time for the actual characters. The deleted scenes between Anakin and Padme might be a bit cheesy, but they are much more natural than what is in the movie. Other scenes could be trimmed down or removed completely. For the Anakin and Obi-Wan relationship to work, I think removing a lot of the "my Padawan" and "yes master' bickering would work wonders.
The character of Count Dooku is the biggest challenge. In my opinion, he should not be a Sith Lord, which detracts from Anakin's fall. Dooku could be turned into a bit the idealist he is described as earlier in the movie. The library scene would be great to have here, if it can be salvaged.