I think the Maul/ Grievous idea could be pulled off by adding a couple of small scenes at the end of EP1. after the scene where Palpatine arrives there could be a small shot of a droid hovering over the pit where Maul fell and you see it go down or better still you see it emerging from the pit with the body of Maul, then cut to the obi-wan/yoda scene. Of course the droid would probably have to be built by some 3D wizard or maybe use an existing background droid to pull this off. then you could have a scene after where you see the body of Maul on the operating table, it would probably have to be in Palpatines ship though. It could mirror the Vader creation scene but be more extreme as there wouldn't be much of Maul surviving as Grievous. Of course there would have to be dialogue changes in EP3 and the stupid accent would have to go, but because his face is hidden beneath the mask there would be no problem with dubbing his lines. with Maul splitting in two as he falls down the shaft this can set up the reason why not much of him survives as Grievous.

I never really liked the whole "taught by Dooku" reason why Grievous would use a lightsaber. Why would Dooku bother training someone who has no ability to use the force. Surely he would have recruited someone who could.

Also the part where Grievous reveals his true identity to Obi-Wan could be just as the lightsaber fight end and obi-wan does the force push. if you look at that scene Obi-Wan looks suddenly angry as he does the force push so that would fit in perfectly.

The only problem that arises from this, however, is the whole name issue. why would he be called Darth Maul in EP1 then General Grievous in Ep3? I think he is only mentioned by name once in EP1 so to help get around this the line where his name is mentioned could be changed, then there would be no problem with his name in EP3, but getting around the whole "General" part could be more tricky