Well I think one option (This option is only valid if you allow to use the restore disk from a completly formated computer) Would be get boot disk (if you dont have one you can easily get one for free). Fdisk the partitions then recreate the partions. Then format the c:\. One warning this will cause you to loose all your data on the computer.
After you completly format the computer try using the restore disk and hopfully it will work.
I think the windows 98 boot disk should include fdisk and gain you access through dos to your c drive.
http://www.bootdisk.com/bootdisk.htm
DOS command needed (I doing this from memory so I not sure if I get this all right it been a good 6-7 years since my dos days.
boot from boot disk
first type fdisk
should be directions then
delete partions and recreate partions
then type format c:\
then try using you restore disk when this is done