A solução para mim é tão estranha quanto a questão em si, mas como eu já criei a pergunta, também fornecerei a resposta.
Tudo o que eu precisava fazer era duplicar um arquivo na pasta de músicas e removê-lo. Depois disso, o Media Player começou a adicionar todos os outros arquivos. Eu já movi todos os arquivos para outra pasta e os trouxe de volta, e isso não ajudou, então a solução é ainda mais estranha.