Basicamente é porque **cada novo índice exige mais tempo para atualizar** o banco em qualquer alteração que afete estes índices. Já vi gente sugerir fazer índices para tudo. Com apenas 6 ou 7 campos, para todas as combinações são necessários dezenas para centenas de índices e maioria precisaria ser atualizada mesmo que altere apenas um campo. O tempo gasto pode afetar a escalabilidade do banco.

Em alguns casos a consulta pode ser prejudicada também. O **espaço ocupado prejudicará o cache** dos dados/índices que realmente são importantes. Além disto acessar primeiro o índice para depois acessar o dado tem um custo e ele pode ser maior que acessar os dados diretamente em certos padrões. E nem sempre o otimizador do sistema detecta corretamente se ele deve fazer o acesso direto.

Da mesma forma as recomendações dos sistemas SGDBs para criar índices nem sempre são corretas.

Além disto cada novo índice é um **recurso a mais para dar manutenção**. Viola o [YAGNI][1]. Inclusive dificulta *upgrades* no modelo de uma base de dados no sistema em produção.

Já vi "especialistas conceituados" dizerem que o ideal é criar índice para tudo e ir tirando os que não precisam. Não consigo imaginar como isto possa fazer sentido. É o pior caso de otimização prematura que já vi. Toda otimização deve ser criada quando você mediu e ficou claro que ela é necessária. Índice existe fundamentalmente para otimizar acesso aos dados.

Os sistemas de banco de dados decentes possuem muitos recursos para obter as informações necessárias para a decisão correta. Estas informações podem ajudar a identificar índices desnecessários também. E como é um recurso para otimizar é preciso revisar com frequência, o que pode ser bom em um momento pode não ser mais no futuro.

Um exemplo típico de erro em criação de índice é quando ele é usado exclusivamente para geração de relatórios esporádicos. A perda para gerar um relatório esporádico sem a otimização do índice costuma causar menos prejuízo que o índice causará no sistema como um todo.

Mas um dos piores exageros que já vi e acontece muito é criar um índice para `colA+colB` e outro para `colA`. O primeiro pode ser usado para obter a mesma otimização que o segundo provê, tornando-o desnecessário.

[Boa referência][4].

----------

Para evitar entendimento errado da outra resposta pelas pessoas que estão aprendendo sobre o assunto vou colocar alguns pontos:

- A perda de performance causada pela criação de índices desnecessários se dá em **qualquer** operação que altere um dado contido nas chaves do índice. Não importa se é `INSERT`, `UPDATE` e até mesmo `DELETE` dependendo da implementação. Alterações que não afetam a chave do índice não causam problemas de performance. Em sistemas de banco de dados que usam alguma forma de [MVCC][2] qualquer alteração acaba afetando pelo menos o índice da chave primária (que talvez seja [clusterizado][3]) já que o dado é copiado para outro local.
- A performance do `SELECT` também pode ser afetada negativamente conforme citado acima na minha resposta. Não ocorre com frequência, principalmente porque o planejador costuma evitar o uso do índice nestes casos, mas **pode**.
- Já a criação do índice beneficia qualquer operação de acesso aos dados que o planejador do banco de dados identifique que seja útil. Normalmente isto ocorre em comparações do `WHERE` mas não em qualquer comparação (isto é importante). Há casos que o índice não ajuda. Índice não é mágico, ele tem uma organização que otimizam algumas relações, não todas. Ocorre também quando se usa `ORDER BY`, `JOIN` e em quando há uso de algumas funções agregadoras. Mas é bom ficar claro que só uma medição pode garantir que haverá ganho. É claro que a experiência pode fazer o desenvolvedor do banco de dados identificar casos simples, mas é preciso ter cuidado. O bom nadador costuma se arriscar e morrer afogado mais que o nadador que tem medo de água desconhecida. Regras gerais, como sempre, podem causar mais mal do que bem. Sempre tem que analisar o caso específico com informações específicas para o caso.

    Um exemplo onde o índice provavelmente não vai ajudar: `WHERE departamento= 'D101' OR admissao > {31/12/2010}`
- De qualquer forma o ganho ocorre em qualquer das operações de acesso aos dados que tenha algum uso das cláusulas acima. Claro que em `UPDATE` e `DELETE` apenas o `WHERE` e o `ORDER BY` é relevante.

Está cheio de mitos em desenvolvimento de software e como consequência softwares com problemas porque há a leitura de informações ilusórias sobre os assuntos. Deixar margem para entendimento errado causa mais mal do que bem.

  [1]: http://pt.wikipedia.org/wiki/YAGNI
  [2]: http://pt.wikipedia.org/wiki/Controle_de_concorr%C3%AAncia_multivers%C3%A3o
  [3]: http://en.wikipedia.org/wiki/Database_index#Clustered
  [4]: http://use-the-index-luke.com/