It's an interesting question from a feminist perspective: how do you do a better job of representing women in a story like this, without it becoming completely unbelievable? And if you expand the roles of the priestesses or queens, it changes the nature of the story sometimes, from action to more of a drama, perhaps, because you wouldn't usually have the women out in the battles.
If you've ever read any of Tamora Pierce's Alanna books, that's a good example of a woman warrior done well--at the beginning of the story, she's 11 years old and wants to become a knight, and switches places with her twin brother, who wants to become a magician. They go off to their respective schools, and the first two books of four delve into Alanna's challenge to keep up in her training, because she's so much smaller than her classmates. She's always the brunt of the bully, who breaks her arm once and nearly kills her another time. Pierce eventually solves it not only with Alanna working waaaay overtime to become stronger and have better reflexes, but also in a kind of Deus ex way, that because Alanna is smiled upon by the Goddess of the story, she is gifted with a magical sword (which actually doesn't live up to its promise, in my opinion, because Pierce is on a crusade to write about "women and girls who kick butt") and makes friends in odd places, who back her up in tight spots. Eventually, though, she becomes the woman warrior that has become what Skar now refers to as the stereotype.
I've talked about this before, how I think that this kind of weakens a true feminism (and by that I mean a feminism that promotes the quality and ability of women, not what some refer to as radical feminism). The feminism of the 70s and 80s often told women that to have power, they had to become men--a perfect example of which is the woman warrior that's become so prevalent in fantasy and historical storytelling. There's so much that can be emphasized about the strength of women in arenas other than physical strength, it baffles me why we have to insist upon women as warriors so often.
Yet--I do like to see a girl kick butt every now and then. I like it when it's done well and believably. I don't like it when it's overused, because sometimes it compromises the other roles in which women have great strength and talent.
I don't know if any of that makes sense. I say, if it's believable, go for it. I haven't seen King Arthur, so I don't know if I agree or not with Skar's opinion of it. In fact, I haven't seen the 13th Warrior, either. It's rather sad. Ever since I've been in grad school, my movie nights have gone down to practically nothing.