Eu me deparei com isso, mas os aplicativos do sistema, como o Bloco de Notas e a Calculadora, também não funcionam no menu Iniciar; e eles normalmente estão perdendo o ícone também. Eu acredito que isso remete a uma variável de ambiente 'Path' super longa e / ou errônea. Como a variável path varia de acordo com a máquina, seria difícil sugerir o que remover, se é que existe alguma coisa, mas você pode procurar lá para ver se isso ajuda.