Eu restaurei o Windows 8 de uma imagem. Depois disso, o problema não apareceu novamente. Meu melhor palpite seria uma atualização frustrada, ou problemas de permissão depois de copiar arquivos AppData do disco antigo, com o aviso de fragmentação sendo um sintoma possivelmente enganoso do problema subjacente.
Por sugestão, coloco isso como uma resposta, embora ainda esteja interessado em saber se há outras maneiras de resolver esses problemas ou o que poderia ter causado isso.