Yeah, the gender-bending thing sounds a little complex to make it into any of Nintendo's games, since they usually don't plan out life stories for their enemies and bosses (as for main characters and heroes, just look at Mario: no effort for a life story).
But then again, how could Birdo have been male in SMB2? That wouldn't explain how she's able to shoot eggs from her "proboscis" (in other words, her big beak of a nose). Then again, Japan is known for releasing the weirdest things, like Pokemon and the roots of Hyakugojyuuichi (it won #1 in some Ultimate Time Waster contest, and is #1 on my list for Stupidest Use Of Media), so that's entirely possible.
And think about it. Both Yoshi and Birdo are dinosaurs (or at least they look similar). I also heard somewhere where in tennis matches, doubles teams always consist of one male and one female for each side. Of course, since Nintendo has been neglecting female characters lately (save for the Zelda series), they had to break that rule with Mario Tennis. Oh, but they found room to make Birdo partners with Yoshi, huh?
I even heard a little article on this in a Nintendo magazine, where when it came to trying to pick female teammates for Wario and Waluigi, which never happened, one of the guys joked, "We don't want to see their girlfriends." But of course Birdo and Yoshi became partners.
It''s hard to save the world when you''re a penguin in wizard clothing.