Found your story about the origins of Nicosias in Sicily interesting.
My husband is a Nicosia and his family on both sides comes from Villarosa in Enna Province, which is about 25 to 35 miles south of Nicosia. Nicosia was a Greek town and many people there still speak Greek. My understanding from the books that I've read on Sicilian history is that Greek was spoken widely in eastern/central Sicily and in the Palermo area(Piani de Greci)until relatively recent times.
We were in Villarosa in January visiting my husband's father, who retired there after 30 years in the US. I don't speak the Villarosano dialect of Sicilian(my American-born husband does), but I found many people who there who speak French(due to living in France and Belgium during their working lives)and Greek. I'm half Greek and I also speak French, so I was able to communicate.
Most of the towns in that part of the island date back to Greek times(the city of Enna is even older)and I noted much of the culture was very familiar to me from my visits to my family in Greece.
Although the story about the Nicosia brothers does have the sound of folk etymology about it, there may be some historical truth to it. The flow of people and goods between Greece and Magna Graecia was constant and it continued into medieval times and later. I'll do some rummaging around in my historical references and see what I come up with