Pues que raro... yo he instalado muchas veces multiboot mi HD utilizando las siguientes configuraciones con Linux (Suse

, Mandrake

y Free BSD

)
98 --- Linux, Me --- Linux, 2000 --- Linux, XP --- Linux, 9x --- 2000 --- Linux.
Si me arrepiento, formateo todo y si utilice 9x o Me junto con Linux, perfectamente puedo eliminar con FDISK todo. Si utilizo algún SO basado en NTFS, con el CD al volver a realizar la instalación, puedo eliminar todo.
No me explico porqué te esta dando tantos problemas.