First, a warning! If you have a Mac and think about partitioning a hard drive, be warned that it is not possible to have HFS- and non-HFS partitions on the same disk! The reason is that HFS writes some information on the sectors of the hard drive where the partition table is usually located. There is a warning in the small print in the Mac help. But: If you have a disk that is already partitioned, say, with three FAT32 partitions, you can select one of them in the disk utility and try to format it with HFS. The disk utility will allow this without any warning! However, it will fail soon with an error message, but then it is already too late: The partition table has been destroyed, and you cannot mount any partition on that drive any more.
But there is help. While the partition table is gone now, the actual data on the drive is not. The solution is a tool called TestDisk. TestDisk scans the drive sector by sector for partitions (this may take a while) and allows to recreate the partition table. I can only recommend this tool, it saved my drive once as I tried the above...
The author of TestDisk, Christophe Grenier, pointed out that, unlike earlier versions, TestDisk now also runs on Mac OS X itself. (Before, it was necessary to run TestDisk on another platform.) Furthermore, it now supports HFS and HFS+ partitions, in case you do it the other way around and loose a Mac OS X rather than a FAT partition. Once TestDisk has found the partitions, you will have to use pdisk to rewrite the partition map.
Samuel Luescher told me he used Data Rescue X and did a raw scan of the disk (Preferences - [X] Ignore Partitioning) to successfully restore the file catalog of his defective HFS partition.