The things you say while testing make me think it is the HDD.
The error itself does not.
Are you completely sure he replaced each component to test as you've said? Like, did you see him with your own eyes? A lot of times, especially in busy stores, people could get shady and just tell you they did this or that while not actually doing it. Think car mechanic scenario.
I have a feeling it's the motherboard. Or perhaps he really is an honest businessman. How do the voltages look in the bios or from a Windows app that reports that? Close to what they should?
Do you have any other HDD greater than like 20 GB to try for now from an old machine or something?
In the meantime, open elevated command prompt and type chkdsk /f followed by the drive letter and :
i.e. chkdsk /f C:
Hit enter. Type y, hit enter. Then reboot.
Let H2S04 guide you with that laptop if it both it and your pc have firewire. He can get the pc to report an error to the laptop that you'd normally not be able to see.
Final thought: I have to ask this to get it out of the way. I know you'd probably have mentioned it if you were, but are you overclocking at all? Perhaps you are and even forgot about it? When I was finding my highest stable overclock, I would also get the kernel-power error and reboots because it was too high. Also check memory settings in bios. Make sure that timings are not too tight, voltage is proper for specific memory modules and frequency is stock too. If all that is, you could raise the memory voltage by .05v and/or .1v for testing.