I don’t think the problem was with “phoenix”.

It was Project Phoenix (resurrection of the Netscape browser). This resulted in the Firebird browser (Firebird and Thunderbird). But Firebird was an existing database that objected to the name. So, we got Firefox instead.

At least that is how I remember it.