The Arduino will boot up as soon as it gets power. Is there any other hardware involved that might need time to initialise? Maybe you have a timing issue at startup. What have you got attached to the Arduino, and what sketch are you running? What happens when you just power up the Arduino?