Hmm, good question. Let's look carefully at how Gaiman describes stories of "male" and "female" type in his essay "All Books Have Genders" (emphasis mine):
Books have sexes; or to be more precise, books have genders. They do in my head, anyway. Or at least, the ones that I write do. And these are genders that have something, but not everything, to do with the gender of the main character of the story. [...]
The novels are a slightly different matter. Neverwhere is a Boy's Own Adventure (Narnia on the Northern Line, as someone once described it), with an everyman hero, and the women in it tended to occupy equally stock roles, such as the Dreadful Fiancee, the Princess in Peril, the Kick-Ass Female Warrior, the Seductive Vamp. Each role is, I hope, taken and twisted 45% from skew, but they are stock characters nonetheless.
Stardust, on the other hand, is a girl's book, even though it also has an everyman hero, young Tristran Thorne, not to mention seven Lords bent on assassinating each other. That may partly be because once Yvaine came on stage, she rapidly became the most interesting thing there, and it may also be because the relationships between the women - the Witch Queen, Yvaine, Victoria Forester, the Lady Una and even Ditchwater Sal, were so much more complex and shaded than the relationships (what there was of them) between the boys.
What possible meanings can we assign to these descriptions so as to interpret them in such a way that the story of Salim and the jinn is "female" rather than "male"?
- Clearly, this isn't about the gender of the main character, the first criterion mentioned.
- It also isn't about inter-female relationships being more interesting than inter-male relationships, as mentioned in the context of Stardust.
- Nor is it about having developed female characters in the story, as mentioned in the context of Neverwhere.
So what is it? What makes a short story about two men "female"?
Well, let's ignore the gender of the characters for a moment, since clearly that's NOT the criterion Gaiman used for the Salim/jinn story, and look again at his comparison of Neverwhere and Stardust:
- Neverwhere has an everyman hero, with many other characters in it occupying stock roles (that also goes for the Sadistic Villains, the Helpful Rogue, and the Hidden Mastermind);
- Stardust has an everyman hero, with another character who becomes the most interesting thing on stage after their appearance, and various complex inter-character relationships.
Still ignoring the gender of the characters, the story of Salim and the jinn fits the second of these categories much better than the first. We have an everyman hero - he's in a strange city, he's looking for a job, he's out of luck. He meets an unexpectedly fascinating stranger who dominates the rest of the story. The relationship between them is more interesting than any standard roles they fit into.
These criteria are probably what defined this story, in Gaiman's head, as female. Again, it can't be anything to do with the gender of the characters, so it must be some other aspect of the story; and ignoring all characters' genders, this definitely looks more like Stardust than Neverwhere.