Did you boot from a thumb drive when you installed? I have seen this problem happen because the drive you booted from (a thumb drive) to install the LMDE system was configured as /dev/sda during the installation process, but the drive which was /dev/sda after reboot was the main hard drive. This might also happen if you installed Mint from a USB hard drive.
LMDE Mate 64-bit, LM16 Mate 64-bit
Debian Xfce 64-bit, Xubuntu 13.10 64-bit, Xubuntu Trusty Tahr 64-bit, Antergos Xfce 64-bit, PCLinuxOS LXDE 64-bit