Windows is protecting itself.... in vista...go into safe mode and navigate to the disc manger and retry to format the partition.

If that fails then you can reuse the XP installation cd to format the partiton or you can try a third party program like partition magic to do it for you!