PC a veces no arranca

Es mi primera pregunta en este foro el cual veo de gran utilidad para los que tenemos una vaga idea de la materia, y por ello os felicito.
Mi problema es el siguiente:
Hace menos de un año, adquirí un AMD Athlon(tm) 64 X2 dual core processor 5000+ a 2.61 GHz con 2 GB de ram y un disco duro de 300 GB ST3320620AS.
El sistema operativo que instale por mi cuenta fue XP profesional a 32Bits, de una version algo antigua 2002. Aunque lo tengo actualizado a través de windows update con el service pack 3 y todas las actualizaciones que van saliendo.
El problema en cuestión es que, al poco tiempo empezó a darme problemas de arranque. Cuando lo apagaba, al volverlo a encender, había veces que no conseguía ni que arrancara:Me di cuenta que hasta que no lo desconectaba y pasaba cierto tiempo no conseguía que volviese a arrancar, y cuando lo hacia siempre me ponía el siguiente mensaje:
"WARNING! Now system is in safe mode.Please re-setting CPU frequency in the CMOS setup."
Lo lleve a la tienda donde lo adquirí por dos veces y las dos veces me contestaron lo mismo, que el ordenador no tenia nada y que podía ser problema del sistema operativo.
Visto el resultado y la atención que me dieron, decidí hacer una instalación nueva y limpia. Elimine la partición donde estaba instalado, la cree de nuevo, formatee y volví a instalar windows,(la misma version). Pero es ahora cuando me he dado cuenta que el problema persiste. He accedido a las BIOS y las he reiniciado por defecto y nada. La frecuencia del procesador por defecto es de 200 y es la mínima que trae y la temperetura creo que es normal.
El caso que ya no se que más hacer y por eso recurro a vosotros antes de volver a la tienda de nuevo, ateniendome de montar un pollo con razón o sin razón. Espero ansioso una respuesta para por lo menos ir un poco documentado y saber si me están tomando el pelo.
Se me olvidaba comentar que la tarjeta gráfica es integrada en placa, y que estas navidades le instale una Nvidia Geforce 8400GS de 512 MGb, pero bueno el problema ya estaba antes de instalarla, la placa base es también una Nvidia. El pC lo adquirí en la casa BEEP por si sirve de algo.
Espero vuestra respuesta, si necesitáis más datos solo tenéis que pedirlos.