"Family fokelore says the family was involved when the English stopped in Crete on the way to the Crusades. England governed Crete for several hundred years around this time".
A ridicules statement/comment. British have never been in Crete and never had anything to do with Crete (other then interfering during the second world war"). Crete was a Venetian colony from 1206-1669 and after that under Turkish control. Before 1206 Crete was under Byzantine control with Saracen invaders from time to time.
To my knowledge, nobody with the name Coultas participated in one of the Crusades. It is not a Greek name and if it is a "New" Greek name it wouldn't be more than 120 years old. It is British name that sounds like Greek like Curtis, Finnis, etc.