There are two meanings of the word Phoenix:
1) From Old English and Old French fenix , adopted from medieval Latin 'phēnix' , Latin 'phœnix' , adopted from Greek 'ϕοῖνιξ' the mythical bird, identical with 'ϕοῖνιξ' Phœnician , purple-red, crimson. In Old French also fenis , fenisces ; Spanish fenix, Italian fenice; Dutch feniks , Middle Low German fenix , German phönix , Danish , Swedish fönix . The English spelling was in the 16th century assimilated to the Latin (fenyce was after It.).

Meanings of the word:
-- A mythical bird, of gorgeous plumage, fabled to be the only one of its kind, and to live five or six hundred years in the Arabian desert, after which it burnt itself to ashes on a funeral pile of aromatic twigs ignited by the sun and fanned by its own wings, but only to emerge from its ashes with renewed youth, to live through another cycle of years.
Variations of the myth were that the phœnix burnt itself on the altar of the temple at Heliopolis: and that a worm emerged from the ashes and became the young phœnix .
-- A person (or thing) of unique excellence or of matchless beauty; a paragon.
-- That which rises from the ashes of its predecessor.

2) modern Latin (Linnæus), adopted from the Greek 'ϕοῖνιξ' the date palm, a date: related to Phœnician.
Various speculations connecting the date-tree with the mythical bird, phœnix (first meaning above) , were current from the time of Pliny or earlier. Also the Latin Carmen de Phœnice, attributed to Lactantius (before 325). Some have supposed a much earlier connection: the Egyptian name of the phœnix was bennu, that of the date (fruit and tree) benr or benra , whence Coptic benne . But Egyptologers hold the two words to be unconnected. Some would explain 'ϕοῖνιξ' the date, as ‘the red fruit’.

Meaning of the word:
-- The name of a genus of palms, distinguished by their pinnate leaves; the most important species is P. dactylifera, the Date Palm.
Source : The Oxford English Dictionary.

Now let's take a look at the etymology of the word Phoenician :
“Adopted from French 'phénicien' , from Latin Phœnīcia (terra), synonymous with Latin 'Phœnīcē' , Greek 'Φοινίκη' the country, from 'Φοῖνιξ' , 'Φοίνῑκ-' , noun and adjective Phœnician .
Greek 'ϕοῖνιξ' also meant ‘purple-red or crimson’ (adjective and noun), the phœnix , and the date (fruit and tree). It is generally held that these are all senses of the same word; but their mutual relations and the primary sense are uncertain. Some start with 'Φοῖνιξ' , Phœnician, as a foreign ethnic name ; others take the primary sense as ‘red’, and see in ϕοινίκη ‘the red land’, perhaps the land of the sunrise, or in Φοῖνιξ ‘a red man’. Phœnicia could hardly be (as some have suggested) ‘the land of the date’.”
Source : The Oxford English Dictionary.

So there is a relation between the words Phoenix and Phoenician .