It wasn't Firebug, that was a developer tool extension. It was first Phoenix which hit trademark issues, and then Firebird which hit trademark issues, which then became Firefox.
Maybe it hit trademark issues, but the reason I remember from slashdot was that phoenix was already a semi-popular open source project in the debian repository, so firefox had to be named from phoenix to mozilla-phoenix. But firefox at the time still named phoenix just ran so much better on windows than linux, it was funny.
Phoenix Technologies, the BIOS maker sent me an email telling us they made a BIOS web browser and our name would confuse things. Under advice from our legal support, we agreed to change the name.
We changed to Firebird and the OSS database project bombed my inbox (and Mitchell's too) for a week with hundreds of nastygrams and though we were in the clear on TM, we didn't want to stomp on the little OSS project so we changed again.
I was at the whiteboard when Jason Kersey of mozBin, mozillaZine, and later Chrome fame came up with Firefox. We had two columns of names, forces of nature and animals and were pairing them up.