I think you need her in it as much as possible to make the love stort convincing. They need to have important scenes together..

I think the classic hate/love story (ala Han/Leia) could also work between Anakin and his futur wife in NPT EP1... but if you ask me, I don't even think they have to be married at some point at all.

But I think the "impossible love story" that Lucas tried to sell us could work if done the write way.

You know: first they hate each other and the moment they finaly get close some event separates them. But whereas in the OT the love story turns well in the end (with Leia rescuing Han), In the NPT the love story turns bad. Anakin arrives too late to save his love (maybe because of Obi-Wan's order to follow another mission or something like that). Just an idea.

It's not very original, but with love story the big deal is making the dialogue believable or at least not too embarassing; and the situation must be desperate.