I have a computer that randomly reboots when the heatsink fan kicks on. It doesn't reboot immediately, which tells me it isn't a power issue (I think). It usually takes about 5 - 7 seconds after the heatsink fan kicks on before the computer instantly reboots.

Does anyone here have any suggestions on what might be the problem?

Computer is using Vista Home Premium. System is less than a year old, Gateway.

Yes, the fan does stop when the reboot takes place. This re-occurs almost every 30 minutes.

I have no problem replacing the power supply, but am unsure whether this would fix the problem.

What are your thoughts on this?