Well this was what I initially thought, since the new graphics card had no fan, just a heat sink. So I recently bought a thermaltake crystal orb for the gpu but since then it still seems to be crashing.
And it is unlikely that the CPU is overheating, I use a thermaltake spark 7+ which had very effective cooling. I will tell you my specs to help any diagnosis:
Asus P4S533MX, 400MHz FSB
Celeron 1.8GHz, 128K L2 Cache
128+256 MB RAM, PC2100
40GB Hard Disk
Xpertvision Radeon 128MB 9200se
Windows XP Home ed. Sp1