I think (and this is a gripe that most people have with the PT) it needed a main villain. Maul, Dooku and Grievous were all throwaways - nowhere near as threatening as Vader was in the OT. Sure, you had Sidious constantly in the background plotting away, but he doesn't really do anything. A main villain that is only defeated in Episode III would be a nice addition. Of course, to avoid this villain from being an exact copy of Vader, a certain degree of moral ambiguity could be added to the equation - perhaps develop the idea that was partially explored with Dooku, in that the villain believes that their actions are a necessary evil to save the Republic. Ambiguous, but not afraid to get the job done. The main characters need a constant, menacing, dangerous adversary.
That brings me neatly on to the next issue; the main characters. I felt that, considering Ewan MacGregor's excellent acting talents, Obi-Wan Kenobi should have been the main character in the PT. His personality jumps around a lot in the PT as we know it, from a stiff young learner to a renegade Jedi Knight and finally to a Jedi Master that languishes somewhere in-between. Instead, Obi-Wan should start as an over-confident and sometimes arrogant Jedi Knight, who believes himself more than capable of training Anakin Skywalker as a Jedi when he is not. This sets him up to fail his instruction of Anakin and go into exile.
Anakin Skywalker's seduction, in my opinion, was handled extremely badly. All of ten minutes of RoTS is dedicated to Anakin's fall, and as a result it feels extremely rushed. Episodes I & II should have established the Clone War, and the slow decay of the Republic, with Episode III almost exclusively dealing with Anakin's demise and his hunt for the remaining Jedi. To retain the shock felt at that pivotal moment in Episode V, the characters of Anakin and Vader should be kept separate - in Episode III, Palpatine has begun to circulate rumours around the galaxy that a powerful Jedi has emerged from the shadows; one evil more powerful than the aforementioned main villain. Anakin, now shrouded in a cloak that hides his true identity, has begun to hunt down the Jedi order. Information surrounding this should be kept to a bare minimum. Only Obi-Wan and Yoda know the truth of Anakin Skywalker's fall, and they keep quiet about it - they go into exile at the end of Episode III, which leaves all of the major reveals for the next three episodes.
One idea that I do agree with from the PT is the idea that a Jedi must not know love - thus, most of the love story can remain relatively unchanged. The thing I would like to see altered would be how this plays into Anakin's downfall. It would be interesting to see Palpatine plant the idea that Padmé is also having a love affair with Obi-Wan in Anakin's head. This would once again strengthen Anakin's hatred for Obi-Wan, which could be fulfilled in Episode IV.
I know I've left out a number of things, but this is the bare minimum of elements that I would change to make the prequels into much more of an OT-ish experience.
Yoda and Palpatine never use lightsabers. Ever.