From what I can find, it was Cayo Hueso before it was Key West. For example, http://www.keywestcity.com/egov/docs/1165259495219.htm

Visiting Southern California, I was confused by a street named Avenida de las Coches - Avenue of the Cars in my smidgen of modern conversational Spanish. One day, I turned on the street to find Wagonwheel Park... coaches as in stagecoaches, d'oh!