Você já estava quase no lugar certo. Abra as Ferramentas > Opções de pasta > Tipos de arquivo, clique no tipo de arquivo XLS.
- Agora clique no botão Avançado na parte inferior da janela.
- Uma nova janela é aberta, clique em Alterar ícone ...
- Clique em Navegar e navegue até Excel.exe (no meu caso C: \ Arquivos de Programas \ Microsoft Office \ Office12 \ EXCEL.EXE) e escolha um ícone ao seu gosto
Repita para qualquer outro tipo de arquivo que você queira alterar.