Assuming you get the grub screen on startup and choose the linux option then you get the message, then it seems like grub is talking to Windows instead of Linux.
Could try entering commands manually on grub command line.
How about
:
root (hd0,1) #assuming linux on second partition
kernel /boot/vmlinuz root=/dev/hda2
boot
If doesn't work try fiddling with it. e.g. kernel vmlinuz root...
It it works enter it in the relevant block in ?menu.lst. /boot/grub/menu.lst. But don't put 'boot'.
Sorry if my earlier advice would have buggered Windows, I don't know.