I think I have a similar problem to you.
# fdisk -l /dev/hda
Disk /dev/hda: 40.0 GB, 40027029504 bytes
255 heads, 63 sectors/track, 4866 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Device Boot Start End Blocks Id System
/dev/hda1 * 1025 ?--> 4866 30860865 c W95 FAT32 (LBA)
/dev/hda2 1276 4803 28338660 83 Linux
/dev/hda3 4804 4866 506047+ 82 Linux swap
Err... surely that first partition shouldn't cover to the end of the disk if other partitions exist!
So since Win98 is pretty much fully installed, one can assume it has overwritten the Linux partitions.
And I don't think "logical" here means logical, as I don't have
any lgical drives yet cfdisk still complains. I don't have partition magic but I doubt it can do any more than fdisk.
What I did wrong was to use DOS FDISK instead of linux fdisk, thus overwriting the partition table and breaking the entire computer.
I then after a while (once enough data had been written to the windows partition to overflow onto Linux) found that grub wouldn't start with error 16, so I temporarily did fdisk /mbr (probably the last thing I should have done), and continued.
Then using a slack cd I tried to mount /dev/hda2, and it said "Not a directory", which is absolute rubbish, and rarely do Linux programs output total rubbish, so something must be severly wrong. So after visiting
http://www.tldp.org/HOWTO/Partition-Rescue/, I came here to drown my sorrows in tears.
And additionally it is "my bedtime" and my older brother will forever think I am a complete numbskull.
Ah well, life goes on.
To conclude I must say there is little chance of recovering from this situation if the data from windows overlaps onto Linux. At least I only lost the mail and addresses, and not the documents.