Not familiar with LMDE, but sounds like you probably have a mixed-mode installation. Win 8 was most likely installed in UEFI-mode. In order to do proper duel-boot, you need to install LMDE in same mode, but sounds like it may have installed in BIOS/Legacy-mode.
Boot into your installed LMDE and run this command to see if drive is using GPT or MBR partitions:
If it shows GPT partitioning, then you have 64-bit Win 8 installed in UEFI-mode. You need to use 64-bit LMDE and make sure the install DVD/USB is booted using UEFI-mode. (There should be two mode choices in UEFI Boot Menu.) First, confirm whether or not that was the problem with your install. Run this command to see the mode LMDE is running in:
[ -d /sys/firmware/efi ] && echo "EFI boot on HDD" || echo "Legacy boot on HDD"
If it shows Legacy boot, then there is a chance that you can use Boot-Repair utility to convert the install to UEFI-mode. You need to have Boot-Repair use the ESP (EFI System Partition) for grub. That will normally be a small (200-550MB) FAT32 formatted partition near beginning of disk. (Open GParted to find out which one it is.) Try that first. If it works, great! If not, you might be best re-installing and making sure to boot the install DVD in the proper mode.
Converting Ubuntu into EFI or Legacy mode
Other useful info on UEFI installs:
If you end up re-installing, be sure to:
* Have backups of anything important
* Have Win 8 recovery DVD's made
* Disable Secure Boot
* Disable Fast Startup
* Make sure Win 8 is fully shut down. (Think it is normally just in some kind of hibernated state. It needs to be a full shutdown.)
* Boot LMDE install disk in UEFI-mode
* Point grub bootloader installation to the ESP, not the MBR of the disk.