Computer Crashing - Motherboard or HD?

I have an HP 735n (athlon xp 2600 512MB 80GB) which is about a year old and it has been giving me various problems for about the last month. I cannot use the System Restore that comes on the HD because it won't work. I do have the CD's and have been able to restore the computer with them. Computer works fine for a short periord after restoring and then starts giving various errors such as.

Boot Record not found.
Or it will load into safe mode when I start it.
Then when entering safe mode it can take 30 mins. to load.

I downloaded TuffTest and ran that, for the hard drive it had thousands of F004 errors which I think means sectors not found.

Then I ran Sandra and the mainboard temp. reading was 66 degrees C.

Sometimes the computer will work fine for a few days then it will just do random slow things, like the screensaver will slow down, or pictures will take forever to load, then when I restart it, it goes into safe mode.

I'm trying to determine, with this computer only being worth $400 or so, if I can fix my problems by purchasing a new 250GB hard drive which I wanted anyway, or if this has other problems, and I should go with a new system. I also own windows 98se and windows xp upgrade if it would be better to somehow format the drive and just load these? Thanks for your help and suggestions.