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?
I have deleted the c drive partition and i am trying to format it using NTFS with a XP pro cd. However the format progress bar stays on 0%. I have also tried to use Norton partion magic to format but with no success.