Laptop won't start up after shutdown

Hello, I have a Compaq Presario V3000 with Window Vista. I have used it for almost 4 years now. I start to notice this problem several months ago.

--- It won't start up after I shut it down, but after 4 to 5 times retry it would start up like it normally should. Someone told me that it was because hard disk failure and when I checked, yes, my hard disk was indeed had bad sectors and heavily fragmented.

--- I bought a new hard disk and install the Windows again. Later I found out that the problem still appear. And now I had to always put it on hibernate, scared that it won't start up forever. But for how long should I do this? From what I heard, it's not good to put laptop on hibernate on daily basis.

I'm not so sure if it was because hardware problem, and I don't think virus was the cause since the problem still appear even after I just formatted the system. Is there anyone having the same problem with me? Can someone help me please?