My partition table got trashed by WinXP.

If I used fdisk and recreate the partition table, will I lose all my data?
Or do I need to used something like partition table doctor? I tried testdisk, but it doesn't recognize the lost partitions when it scans the drive.

There are probably safer ways to do this.

gpart can guess partition tables and write them. Read the man pages very carefully before trying it.

parted can list current partition tables, but I find it difficult to safely re-write them.

cfdisk can show you the current partitions on a hard drive, and you can re-write the partition tables. for example, if you have only one hard drive, start cfdisk from the command line: cfdisk /dev/hda. It should show you the partitions on /dev/hda. If they look ok to you, use the tab or arrow keys to select Write, and re-write the partitions tables.

Hopefully, you won't loose anything. If you do, I hope you have a recent backup you can restore. If not, perhaps it would be a good idea to begin keeping a backup around for such days as this.