I just installed LMDE this morning and had the exact same problem while trying to install Inkscape. Through command line I found the problem was that I had to update the repositories. Then mintinstall, the software manager, works.
This is the command:
sudo apt-get update
Note: I did not find any way to update the repositories in mintinstall 7.3.3 and THIS is a huge flaw. The fact that the software manager does not output the connections issues is also a terrible behavior.