Tenho a seguinte experiência relativa a restauros de sistema em Windows XP :
1 - Se uso um ponto de restauro automático criado, p. ex., ao instalar software ou actualizações, o restauro não se completa, indicando uma mensagem como a que referes;
2 - De vez em quando, uma ou duas vezes por semana, crio os meus próprios pontos de restauro; quando uso esses pontos para restaurar o computador, corre bem ...
Verifica se tens outros pontos de restauro mais antigos ...