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.
All the first 3 names were taken. They probably had to bribe even the holders of the Firefox trademark to get it (though the terms were never disclosed).
Mozilla was sued to rename Firefox (like I said) by one Phoenix Technologies. If I remember right, they picked two bad names before picking "Firefox" but I don't remember the other one.
I think Firebird was the second name they tried to use that was already taken. They were definitely sued by Phoenix Technologies for one incident. Bryan Lunduke has a podcast explaining the history of this but I saw the one about Phoenix on the Wikipedia page before posting.
