Boas,
Olha a mim aconteceu-me exatamente a mesma situação, de início a situação era semelhante à tua, dava-me o tal erro do explorer, e pedia para reiniciar o dito.
Acontece que mais tarde, o explorer reiniciava e voltava constantemente a dar o mesmo erro, mesmo depois de reiniciar o portátil e até entrando em modo de segurança a situação acontecia.
Estava a meio de um trabalho para entregar que infelizmente ainda não tinha guardado na pen, já para não falar em centenas de fotos da minha lua de mel, filmes etc., pois não conseguia mexer em nada, assim que o windows iniciava lá estava o maldito erro do explorer que frizava o computador. Nem pen's aceitava, nada, quanto mais criar nova conta, como muito bem disse o Romani...
Por sorte lá me lembrei de um live cd de linux, iniciando pelo mesmo, conseguindo assim salvar tudo o que era de importante.
Solução que arranjei, foi mesmo a formatação.
Mas também há males que vêm por bem, já tinha o vista instalado há quase um ano sem nenhuma formatação, sempre a instalar e desinstalar cenas, portanto já fazia falta.
Agora a razão do acontecido não sei explicar.
No meu caso foi enquanto assistia um video que tinha sacado naquele instante.
Ãgora, terá sido problemas com conflitos de codecs? Não me parece, pois tenho o Klite mega codec pack, assim como muitos e sem problemas.
Aponto mais para que tivesse sido um virus manhoso, que até poderia estar contido no tal video.
)