Reseat your RAM and Video card if you havnt already done so. Also, check that there are no burst capacitors on the motherboard (The things that look like little wee silo's.
The fact that the problem is still there after a fresh format, would lead me towards hardware failure. It could be a number of things causing the problem, motherboard, RAM, video card, CPU.
When did it start freezing? Have you added any extra PCI cards or done anything inside the case lately? Any power outtages?