another posibility is that motherboard is older and doesn't recognize HDD. normally if you leave it on AUTO it should be fine. meny people don't like that since it takes longer to boot (HDD is recognized every time you turn on PC).
If this is what happened and then you replaced drive for bigger one, you could also see the issue. also there could be problem with your power supply. HDDs require more juice to start spinning till they reach operating speed. old power supplies like 350W are long obsoleted since new machines need more jiuce (big fat CPU, more RAM, Fast graphic card, HDD, CD/DVD burner, more fans etc. and they all need more power). standard these days in the 450W range (or more). you can see if the problem goes away if you remove some hardware (not the keyboard of course).
you should also check if your HDD and motherboard have compatibility issues or if there is need for startup delay (some HDDs take longer to spin up to the right speed and until they reach the speed, they don't "work", this is worsened by weak PSU). if this is supported it should be in your motherboard BIOS.