Firefox addons are usually the cause of interface bugs. Have you installed (without necessarily uninstalling) addons, specially addons that may affect this search functionality? Keep in mind that some addons modify firefox's configuration permanently, and do not revert the changes when they are disabled or uninstalled. Most of the configuration information is kept in the profile, so simply reinstalling Firefox keeping the profile probably will not help.
If you believe it could be caused by one of the addons you installed, you can try disabling it (and restart firefox), and if that doesn't solve it, you can search the web to find out if that addon/s can cause this problem.
Thanks. I took you advice, but before I went and started disabling random addons, I started Firefox in safe-mode. I tried the search button in this mode and it worked. I start Firefox normally and strangely the search button was working. Very odd, but it's working. – Adam Harte – 2009-11-09T23:02:27.530