Welcome to the update process in a rolling release based on a 'testing' base?!
Don't forget that Synaptic and Mint Update are both just front ends to the apt-get commands and I would suggest "broken" may mean something a little different to each app; therefore the error message may mean something a bit different. I also got this error message and below is how I solved it. BTW, the problem lies with a library file that is a dependency but was not picked up for upgrade by Mint Update. Can't remember its name now and it doesn't matter because the 'fix' is universal.
Background - Aptosid is a distribution based on Debian Unstable (Sid) which is not too dissimilar to LMDE; a little more bleeding edge perhaps. They are are a pretty conservative bunch over there (considering what they work on) and they have a simple, non-negotiable method for doing updates on a rolling release - do it any other way and you get no support basically. This approach has always fixed my systems when this sort of "fix broken" when there are none problems.
This is their approach:
NEVER do an upgrade with the X server running. Did I mention, NEVER do an upgrade with the X server running!!!
Log out and at the Login screen issue Ctl-Alt-F1 to go to CLI.
$ Login as root - or in our case login as user then use 'sudo sh' to get a root shell - remaining commands are issued as super user -
# init 3 - stops X server from running, becomes single user mode
You may have to press Enter a couple of times to get your # prompt back
# apt-get update && apt-get dist-upgrade
have a look at what it is going to do, it will be at least equivalent to a full Level 5 Mint Update, including kernel updates.
Accept the changes, and wait for completion. If nothing really major like the kernel or libc has changed to can issue this command,
# apt-get clean
# init 5 && exit
You should then return to the graphic login screen and away you go.
However, to be extra careful issue this command instead of init etc,
Fixed it nicely here, updated the "broken" library and returned to normal operation.
I still believe that one of the main areas the Mint developers will have to pay some close attention to as LMDE moves into a more "dynamic" Debian testing environment will be this whole question of how to do updates fully and efficiently. Personally, I think the whole 'grading' system is useless in a rolling release; by its very nature a rolling release implies you keep the whole thing up to date all the time; ie it just keeps rolling along. Like that big river you have in the US?
hope this helps,
Life isn't about waiting for the storm to pass...
it's about learning to dance in the rain.