Male medusas do not bother me at all; as has been said, maedars have been around for a long time. (Also, this way I don't have to come up with explanations about where the baby medusas come. Although compared to the sphinx, medusas are easy.)
Nothing wrong with them. I've had a male medusa npc in my last campaign. Seemed like a good fit in a dungeon filled with classic monsters with a twist, which would lead up to planescape-ish adventures, but some of my players disagree.