I am the King Under the Mountain, and this is the first post on this thread!
Ok, so, I loved this story when I heard it on Beneath Ceaseless Skies, and I loved it more just now. Cheyenne Wright beats the hell out of whoever reads the stories over at BCS... which is no insult to BCS, because Cheyenne Wright beats the hell out of pretty much everybody. His voice definitely added a lot to the story. I liked the way he actually slowed down during the action scenes, rather than speeding up, which did a good job of invoking a real man reliving a painful memory, rather than just an exciting story told on a podcast.
As for the story itself, I enjoyed the light hand with which the author played with themes of alienation, honor, and finding your own way in a hostile world. The characters of Mr. Hadj and the nameless narrator were both surprisingly deep, despite being portrayed in few words. And, of course, the fantasy elements were lots of fun, and likewise very subtle.
A brief aside: when my wife and I were in Egypt, our friend Jon took us on a walk through the Necropolis, a working neighborhood situated in a centuries-old graveyard. Squatters have moved in over the generations, putting roofs on the tombs and wiring them for electricity, water, and satellite TV. It's not a great neighborhood to live in, but it's safe to walk in and, unlike the rest of Cairo, quiet. One particularly awesome thing I saw was a painting of the Kaaba and the faithful marching around it on someone's external wall. Jon confirmed - I'd studied Islam in college a bit and suspected it myself - that this marked the owner of the home as a hajji, or someone who has performed a pilgrimage to the Kaaba himself.
Anyway, for the curious, that's what Mr. Hadj's name was (probably) a reference to. What the narrator's father was doing was ensuring that his son would apply a fairly high honorific to any man of his father's people he met - at best, anyone he used that title with would be justifiably flattered and at worst, probably just bemused and also flattered.
One of the best things about this stories is how many questions it raises in me. Was Mr. Hadj a real hajji, or was he just amused at this half-Arab kid using a title he didn't deserve? What was Mr. Hadj's crime, and what contexts did it give their relationship?
For myself, I like to imagine that Mr. Hadj had almost completely lost his faith before he met the narrator, and that suddenly being called "Mr. Honored Pilgrim Sir" is what started him down the path to his own redemption... but that's just me. The story doesn't tell us, and that's part of what makes it so beautiful.