I started up my first game and poked around a bit, then I saved and on my way out reviewed the Achievements so I'd have an idea of things to try to do. To my surprise, I'd already earned an Achievement. Playing for both teams ( Play a hero of each gender ). Neat trick seeing as I have only played one game with a female hero. So I'm guessing the achievement is awarded on selection of a female avatar and doesn't check to see if a male avatar was ever played.
Did it maybe count the tutorial hero? Not sure if that would matter, but that's the first thing that leaps to mind.