In practical terms, how long is it taking for each courtier to get through their stories?

How many players do you have? I figure between half an hour and and hour and a half per Story. My estimates might be a bit off, but given con experience, it feels about right. It's totally reasonable to play an entire game of 1001 Nights with between 3 players (usually 3 Stories, sometimes only 2) and 8 players ( between 3 and 5 Stories)  in 4 hours. There's variation in this, since when a Story ends is in part driven by how quickly the Storyteller wins dice. Sometimes, especially with a lot (more than 5 people total) of players, there are lots of things happening quickly, and so things resolve more often and the Storyteller pull sin dice fast. With a smaller group, or a group declaring fewer interests, it can take a bit longer.