Encontrei. Outro plug-in estava causando o Firebug não iniciar corretamente. No meu caso, este foi o Microsoft .NET Framework Assistant. Desativar este plug-in resolveu o erro.
Acabei de instalar o Firefox 3.6 (atualizado), e quando tentei instalar o Firebug (1.5) ele diz 'addon installed' mas não há sinal do Firebug em lugar algum. O F12 não faz nada, o ícone do 'bug' no canto inferior direito não está lá, e nada está no menu Extra também! Qualquer ajuda apreciada!
Já experimentou um novo perfil na sua instalação do Firefox?
Start -> Run -> "firefox.exe -profilemanager".
Inicie um segundo perfil (provavelmente terá que criar um novo perfil) e instale o firebug lá. Se funcionar bem, você tem um problema com o seu perfil atual. Caso contrário, há algum problema com a instalação geral do firefox.