Eu tive um erro diferente ( Como reparar Instalação do .NET framework 4 no Windows 8 ) onde uma DLL estava corrompida, então presumi que isso poderia estar relacionado a ela. Em outro computador, encontrei o wmploc.dll
que contém os ícones do arquivo de mídia. Eu substituí o arquivo e depois de reiniciar os ícones estavam de volta. O WMP também está de volta na lista de Programas Padrão.