Invalid Partition Table after Fdisk /mbr

I’m working on a system that had a Windows 95 upgrade (OSR1). The hard drive is infected with Stoned.Monkey.F, which modified the master boot record. In attempting to clean it out, I booted with a windows95 boot disk, then did an fdisk /mbr to repair the boot sector. Now when I try to boot, I get an invalid partition table message. Is there any chance of recovery from this, or is it now time to repartition and reformat?