A love triangle could have been interesting. I always felt they should have went with that more in Ep. III, it was the original intention, as you will see if you read the script (Palpatine, pretending he does not know of Anakin and Padme's situation, let's Anakin in on the rumors he has been hearing about Obi-Wan being involved in some sort of scandal with a certain young senator. It is a great scene that really shows Palptine trying to cause Anakin to doubt Obi-Wan and Padme loyalty), but for some reason they cut that scene leaving only small hints of Anakin's suspicions. I think it should have been more clear that Anakin was begining to believe that Padme had been having an afair with Obi-Wan, and that Anakin thought the baby wasn't his, and that the Jedi Counsel were somehow covering for Obi-Wan and working against Anakin (maybe the Darkside is like certain drugs and make you paranoid? :)
However, I am not sure how I'd feel about a real triangle, maybe a something like Obi-Wan liking her, and bigshot Anakin comes in and sweeps her away. But to me, I think more focus should have been on the sense of brotherhood between Anakin and Obi-Wan, in which case, I think they would be less likely to try and steel each others love interests. Could have been that Anakin had been extremely fond of Padme, and really liked her. While being her body guard, Obi-Wan spends time with her and she starts to like him, and he starts to like her too, they would have fallen in love, but Obi-Wan, being faithful to his friend, backs off and acts like he is not interested in her. She is disappointed he did not share her feelings, and after some time falls for Anakin. Then we would have Padme being the someone Obi-Wan truely loved, but forbid himself from, because he did not want to hurt his friend, now Anakin and Padme are married and once Anakin starts acting out of the ordinary, and suspicions of Sith influence arise, Obi-Wan feels the need to protect her, and takes her to a safe place. Anakin hears or sees that they ran away together, and decides they have both betrayed him.
Man, there are SOO many ways to make this work. Get so sick of people saying, "You honestly didn't expect them to be as good as the originals did you? Because that would have been impossible!" Looking at things realistically, there is no real reason why they could not be as good as the old ones, and certainly no excuse for them to have been so over the top awful as they were.