Meu palpite é que você não está alterando o ícone do executável real, mas sim um atalho. Mesmo que pareça com o executável; nem todos os atalhos têm o ícone de pequena casca. Execute o programa, no Gerenciador de Tarefas, veja o que é o executável real e altere isso. Se não atualizar, reinicie o 'Windows Explorer' no Gerenciador de Tarefas.
Para mais ajuda, precisamos conhecer o programa em questão e seu método de alterar o ícone.