Heh. Birdy the Mighty has a very similar concept. Male/Female gender switching.
OP, I know I'm getting farther and farther away from the target date, but Slayers is also pretty good. The Everything Slayers torrent has all 70+ episodes the 5 or 6 movies and the OVA episodes. Slayers is also getting a new season this summer. But you probably already knew that.