fixmbr that you tried only cleans the main boot record for windows, so that doesn't help you at all...the problem resides in the real partitions. I'd say you should now make backup of your HD and re-partition it...I've had a similar situation, where I had a working linux on HD but a newer one couln't be installed because of the partition table that was somehow screwed up. and I only could help it by deleting all the partitions and re-creating them..
anyway, whether you choose to redo partition table or not, I suggest to make backup of your data..there might one morning be a note for you that the partition table is unusable
ok, that'd be bad..but might happen.
another chance is, that your fedora installation needs a different kind of partitioning setup than your mandrake...in that case, you don't have much other choises but wipe out the existing table and re-create it.