Problem: I used GParted in Ubuntu 8.10 64-bit to resize an ext3 partition and then installed Windows Vista on a new NTFS partition. This resulted another ext3 partition to disappear and partition table to go corrupt. Other partitions still worked, but no disk management tool did (Fdisk, GParted or Disk Management in Vista). Luckily all important data had been backed up.
Solution: TestDisk (available for Windows, Linux among others) is a true supertool for analyzing disk contents and recreating partition table to match disk contents (among other things). It analyzed disk contents, showed a list of partitions available on the disk and allowed me to select valid ones. It then recreated the partition table and without losing any data. TestDisk was even able to recreate lost extended partition. It seemed that either Vista or GParted had originlly made extended partition size invalid.
TestDisk even allows copying files from partitions before making changes to the partition table. This functionality was not perfect as it resulted a loop with one directory causing a large number of bogus files to appear on the disk - it was necessary to kill the process.
The user interface has some learning curve. I had to run the disk analysis for several times (>1 hour/analysis) before I realized that it was necessary to select all valid partitions from the disk and not just the one that was missing.
Once before I have been able to recover from similar situation by using a hex editor to edit partition table, but this was much more pleasent experiece.