You can't format a deleted partition. You can only format an existing partition. So your story isn't complete.
What disk (SATA, IDE?), how big the disk, how big the partition, what version of XP (original, SP1, SP2, SP3)?
How did you delete the partition? How did you create the new partition (if you did)?
Why did you delete the partition?