I guess you have auto-detect hard disk on in your bios. You could try to manually (or by scanning for new hard-drives) select your hard-drive in the bios, so it doesn't have to search for it while booting.
I guess it goes something like this: you boot your computer, the hard-drive is a bit lazy in spinning, the auto-detect doesn't find anything, because the drive isn't ready yet, the computer continues to boot, hard drive is ready, but not found by detection, so you can't boot, you press ctrl+alt+del, hard-drive is still spinning, so it starts fast the second time, is recognized by the bios and everything works fine.
So with selecting it in the bios, your pc knows there HAS to be such an hard-drive. Therefore it waits a little longer for the drive to come up, what gives the drive the time to start its engines...
JohanFH
Well, unfortunately in Phoenix bios I can't change any hard disk options, it's automaticly detected. But I do something else: I exclude all USB and networks drives and hdd from boot order. Why? I notice, somethimes when booting sata hard disk was at bottom of list, below usb and network drives. Maybe this helps, I will see tomorow when my notebook cool down.