Recover a lost NTFS partition on the cheap?

I had a workstation running XP. Filesystem was NTFS, single partition over the entire drive. After an attempted XP repair install, suddenly the NTFS filesystem is just gone and the drive is showing up with a single 10Mb FAT32 partition with virtually nothing on it, except a directory with a smiley-face character (e.g. not good).

I've run all the tools I could find on the UBCD and nothing is able to detect the missing NTFS partition. I've run some low-level tools on the drive and it checks out ok. I'm not ruling out hardware, but that's not really my question.

What are my options here for recovery?

Update: I was never able to recover the partition, but I did recover a lot of data using PhotoRec (from the same guys who do TestDisk, recommended in the answers below). The name is misleading as it doesn't only recover "photos", as I had originally thought. It does some 180 file formats.

Solution 1:

The one, the only. TestDisk. Here's a rundown of the entire process.

Solution 2:

Gpart (not gparted) can recover missing partitions, by guessing where they are. It's a Linux tool, so it's on some of the recovery liveCDs.