Invalid Partition Table

So my brother wanted to put XP on his computer, we deleted an extra (32-bit Vista) partition (64-bit alongside). Then, when we restart, we get an "invalid partition table" error, formatting the drive (using XP) doesn't fix the issue (trying with Linux now). Any ideas on what we can do?

 

Are you planning to wipe the whole drive, or trying to salvage Vista X64?
If wiping the whole drive, boot a GParted CD and delete all partitions.
If salvaging Vista, boot the Vista X64 disc and run a startup repair.

 

Was trying to save x64, but we decided it would be better to wipe it.
That's the weird thing, it wouldn't see the disc under available drives.

EDIT: holy poo, Linux did it.
EDITING for instructions...
1) boot up livecd
2) open up gparted
3) (space was said to be unallocated), chose the new option
4) asked me to create a record or something (vague text I don't remember), chose MSDOS
5) partitioned the disk
6) installed xp

Thanks Hep.

 

GParted wouldn't?
Make sure you've got an updated version.

 

Not sure what you mean, GParted (that is the disk partition editor, isn't it?) was on one of my old Ubuntu CDs.

 

Gparted is a live CD I use. Also make sure that you formatted NTFS, MSDOS implies FAT32 and is an inferior filesystem.

 

The MSDOS was some setting right in the core of the HDD since after I created that setting, it allowed me to format the disk using NTFS.