Can you try to load another OS temporarily. Do you have an old Win98 disc lying around. This will at least rule out the hard drive and any other hardware that PC World might try to blame, and you can always format again afterwards.
If it works and everything on the HD is clean I would suspect a faulty recovery disc.
One point may be worth mentioning. I got one of these things with my PC and got all sorts of errors when I ran it from the CD-RW drive. Decided to try the DVD drive and worked without problem.