Since i use firefox-1.0.6 with gentoo ~x86 i often have to clear the firefox cache for the bug search to work (i.e. ALL bugzilla). The site always works with konqueror.
Could you please specify what "fails" means here? I sometimes get timeout or 500 at times when bugzilla is responding really slowly, but that's probably not what you mean.
I get an javascript error in the javascript console, "quicksearch" is not defined. Without this function the generated request gets as response "no valid bug id" or similar (this morning it works after clearing the cache). Here is the snippet from the buglist request page: onsubmit="QuickSearch(f.id.value);.:" As mentioned, it helps to clear the cache and to reload the bug list request page.
I have a similar proble, in fact I found this bug doing 'ALL firefox' (not logged in) and it replies that 'ALL firefox is not a valid bug number or bug name" or something similar, in a red box. Going back and clicking search again finds the bugs just fine however.
Bugzilla upgraded, reopen if it's still an issue.