As you say, the evidence is "not unassailable". OED Online gives two views of the development of 'Phoenician'. One view presents 'Phoenix' and 'Phoenicia' as cognate, the other does not. As cognates, this development is shown:
Ancient Greek Φοῖνιξ Phoenician probably represents a use of ϕοῖνιξ dark red (adjective and noun) < ϕοινός red (perhaps originally blood-red < the same Indo-European base as bane n.1) + -ικ-, suffix forming nouns. The chief sense of ϕοῖνιξ in Greek is dark red, tawny (e.g. of a bay horse, of a rusty-red river); the sense ‘purple’ appears to be secondary. The use of this word for the Phoenicians is therefore probably to be explained as denoting reddish or tanned people, rather than those who imported purple dye (for which the Greek word was πορϕύρα: see purpure n. and adj.).
The parallel story associates 'Phoenician' with either the name of a clan of a Hebrew tribe, or an Egyptian word, attested considerably earlier than the clan name, designating "countries of the eastern Mediterranean seaboard". The Egyptian word is related to another Egyptian word meaning 'carpentering', and the view presented by OED Online points out that Phoenicia was a primary source of the timber used in Egypt:
An alternative view is that Ancient Greek Φοῖνιξ represents an assimilation to the form of the ancient Greek adjective of a derivative of the Semitic word for the madder plant Rubia tinctorum, Arabic fūwa, apparently related to Hebrew puwwāh, pū'āh, the name of a clan of the tribe of Issachar, which has the gentilic form pūnī. However, the ancient Egyptian word fnḫw is attested very much earlier (from about 2300 b.c. onwards) as a word for the countries of the eastern Mediterranean seaboard, and is also related to a word meaning ‘carpentering’, which appears significant in view of the fact that Phoenicia was the chief source of good timber for Egypt.
["Phoenician, n. and adj.". OED Online. December 2015. Oxford University Press. http://www.oed.com/view/Entry/142593?redirectedFrom=phoenician (accessed January 11, 2016).]
The OED Online scholars seem to prefer the view of 'Phoenicia' and 'Phoenix' as cognates; however, they are anything but unequivocal about their preference.
Online Etymology (OE) is also equivocal about the origins of 'Phoenix' and 'Phoenicia'. The folk etymologists that produce OE, however, endorse the explanation that the use of the word ϕοῖνιξ meaning 'dark red, tawny' is associated with people "who imported purple dye" as opposed to the more probable denotation of "reddish or tanned people" (OED).
About 'Phoenix' (Greek ϕοῖνιξ), OE has this to say:
...literally "purple-red," perhaps a foreign word (Egyptian has been suggested), or from phoinos "blood-red." The exact relation and order of the senses in Greek is unclear.
(From "Phoenix", at Online Etymology.)
And about 'Phoenician', OE gives this:
...perhaps literally "land of the purple" (i.e., source of purple dye, the earliest use of which was ascribed to the Phoenicians by the Greeks). Identical with phoenix (q.v.), but the relationship is obscure.
(From "Phoenician", at Online Etymology.)