That indeed sounds very suspicous, you're right there is no HAL in win9x/me and such file does not exist.
Has there been any installation attempts of winnt/2k/xp on the system? Perhaps somehow nt os loader was accidentally installed?
Besides the previous suggestion you can give this a try as well:
Get into Linux and backup the current partition bootsector
dd if=/dev/hda1 of=bootsect.old bs=512 count=1
put bootsect.old somewhere safe outside the harddrive, such as a floppy disk.
Boot with a dos floppy disk(put bootpart on there or somewhere in c: drive where its accessible).
BOOTPART WIN95 BOOT:C:
Which will rewrite win95/98/me bootsector back into the partition
Also you need to make sure GRUB is configured properly(ie for the Winme entry it chainloads hda1 which should be (hd0,0))