I think part of what made their relationship so barfable was not just the lack of chemistry, but the utter lack of sympathy we (I) felt for the characters.

Padme Amidala is just a Leia clone with the sharp edges smoothed off, and where's the fun in that? Her claims to fame are her time in the "legislative youth program" and peaking, politically, at the tender age of 14. Leia is like the girl you know who prefers to hang out with the guys and can out-drink, out-swear, and out-fight any of them. She puts up a frost queen front, but you know there's something tender deep down and you'd do anything to melt it out of her.

Han is the kind of guy every guy wants to be, and every girl wants to ... well, I don't know, they probably want to do something to him. He's got a fast spaceship, a best friend who beats up his enemies, and a big gun. Anakin is a dangerous sociopath who lived his entire life in slavery--first to a flying bug, and then to an order of militaristic religious zealots. He left his mother to rot in slavery, after which she was eventually raped to death by Sandpeople. And he had a bad haircut. Even if you had never seen the OT, you knew you didn't want to be Anakin, because he had been dealt a bad hand by life and he was playing it poorly.

Anakin and Padme ... I don't think even chemistry could've saved that dreadful pairing.