W XP boots extremely slow

I have a clients PC running W XP with 40gb HDD 512 RAM 2.4 P4. He reported that the PC was very very slow @ boot and would recycle at boot. It would keep booting. It would do this in normal startup and safe mode. I looked at the drive and there was no file system just unpartitioned space. I created partition, formatted and installed XP. The system boots ok but is still very very slow. I mean 3-5 minutes. I have the boot order A,C CD.
Thanks