Occasionally, with no specific pattern, I (and others) found that when LMDE ran the update function, and you tried to do the update, the update function erred out with a notification to fix broken packages.
While this can be done from Synaptic package manager, this didn't clear up the problem most of the time.
Searching this and other forums, a problem was identified with one of the Lib packages. For a while, just not loading this, and waiting for a corrected update, solved things.
Now, however, I find that this solution no longer works. For a while, loading everything except every package starting with Lib name worked, and then loading these seperately.
What just worked for me, as of March 19-20 2011 (I have LMDE on my laptop and desktop), has been to load just a few at a time. I started with 10, then 30, then everything else. The problem seems to not be with LIB packages, but either Mint Update doesn't like to load a great many, or some other daemon needs incense burned and virgins sacraficed.
Generally speaking, loading just a few at a time seems to work. If you start out with just a few, and gradually increase, it works. Specifically, I loaded 10, 30, and then I think 63 remained (this was on my desktop, which I don't run as often as my laptop, as far as number of packages goes). Even with my laptop, the general pattern of roughly a bakers dozen, then about twice that month, then the rest, works. Do note, however, that everything does load, and this avoids the error notice. I've had this work for three different updates. Sorry, I don't remember when the others happened, but the first was when the LIB solution was proposed. I can't remember for sure, but I think I was able to load all LIBs that time.
Hope this helps. And, hopefully, it will help lead the programmers to a solution.