The Karaim and Tatar communities in the vicinity of Trakai date from the time of Vytautas. The Karaim spoke a similar language to the Tatars, but they weren’t Muslims, instead they professed a heterodox version of Judaism. These people may have worked as castle guards, and they seem to have regarded Vytautas as their patron and protector. There are a number of versions of the legend of Vytautas’s horse available on the internet, but none of them include this detail about women being banned from the castle. Women like Vytautas’s queen certainly lived there. If you look at a map of Trakai, there are many lakes, and the legend purports to explain how one of them came about.
Here’s my translation of a rather elaborate version of the legend. The teller was an ethnic Karaim named S. Charčenko.
Like a divine scourge, the great prince Vytautas pursued the half-wild Tatar hordes that wandered the endless southern steppes, and he soon moved Lithuania’s borders to the shores of the Black Sea. Doing the prince’s will, the unvanquished warriors were long away from their native lands, and the awesome echoes of praise for the prince’s might were heard far beyond his homeland.
Once the great prince’s troops crossed the borders of old Lithuania and soon lost themselves in the boundless fields of the wild steppe. A hot summer passed, then a golden autumn, and all Lithuania was covered with a thick layer of dazzling snow, but there was still no news from the departed men. After the severe winter, under the warming rays of the spring sun, the snow quickly melted, and the runoff began to fill the lakes. Water levels were constantly increasing, and finally the Galve and Totoriskes lakes flowed together, creating a boundless, sparkling expanse of water. The whole Karaim village (?) was flooded, the modest homes forming a series of pitiful islands.
Old men and women holding children escaped to a high area, where they discussed worriedly their hopeless situation. Finally, recognizing that they were powerless, they decided to turn to the great prince for help. Wasting no time, they got in boats and rowed up to the walls of the castle, and a noisy crowd formed at the gates.
Seeing from a high window of his palace the women and old men, the prince gave the order to lower the heavy chain bridge, open the gates and bring the unexpected guests to him.
“Great prince, light of our eyes, all the people utter Your name in awe. Save us, o radiant lord of nations,” the women cried. “It’s already been a year since our husbands and brothers went out to fight your enemies, and since then there has been no news of them. As you see, our homes are flooded and there is no one to save us. You are our father and lord, don’t leave your faithful people in this state.”
Vytautas looked out at the Karaim village, and his brow wrinkled.
Around it glimmered into the distance a large expanse of water, with only the far hills on the horizon and the roofs of the Karaim homes visible.
The great prince didn’t waste time contemplating the scene. His face brightened suddenly, and he said, “Go and don’t be afraid, I will soon join you.”
Indeed, they didn’t have long to wait. Hardly had the crowd arrived back at the shore, when Vytautas appeared on his warhorse. All of old Lithuania had heard tell of the miraculous features of his horse, and it was repeated to children in whispers how the Zemaitian priests had brought the horse to the great prince as a gift.
When Vytautas reached the shore, he turned the horse suddenly and with a gentle hand started to give it water. Like a miracle, the water surface seemed to waver, and then the level began falling. The wet shacks soon appeared, then a thin line of land between bodies of water, and finally the whole broad line of the village was restored. The spring sun hadn’t even dried the ground when the gardens became fresh and green, as if there had never been a flood at all.
The amazement of the Karaims knew no bounds. “That prince, he is like our own father! Let his name ring out forever over the land, and let our descendents keep the memory of his miraculous horse for all time!” Blinking with astonishment, they ran thankfully to the great prince, but he was gone. Having done the will of its master, the noble horse rose up like a whirlwind and disappeared into the dark forest. Overcome with happiness, the women didn’t contemplate the wonder they had just witnessed, instead they took their childrens’ hands and went back home. But the wise old men stayed, nodding their grey heads and scratching their beards. Deep in thought, they finally concluded that for such a glorious prince, a horse like that was only fitting.
The next morning, the news spread that a new lake had appeared, and the water of this lake had some strange properties: it contained no living things, and it smelled like the great prince’s miraculous horse.
Source: keliauk kitaip aruodai
There are other legends concerning Trakai, for instance one about a secret tunnel between the castle and the Dawn Gate (Aušros vartai) in Vilnius. About the banned women, I think that by the nature of oral literature, details change in the telling. This one doesn't seem to have any basis in historical fact. Maybe someone has confused the Grand Duchy with its northern foe, the Teutonic Knights?