Very Slow Boot

slow boot
My hp4455 pavillion with a celeron 4ooMHZ processor has just had a new HD put in (WD 20G, 7200RPM) and now when I boot it takes almost 3minutes or more. Seems to hang right before it detects the HD. I have the Bios HD setting set to Auto. I have tried setting it to user with the sectors, size… and all that crap but it still boots incredibly slow. Any ideas???? Scott