I'm running Mint 13 - Mate desktop environment.
Everything was running great until I tried something and messed my system up. I was looking through some links I had saved, and "just for the heck of it" I wanted to see what the info in this one would show. http://www.ubuntugeek.com/cleaning-up-all-unnecessary-junk-files-in-ubuntu.html
Looking through the options, the best I can determine when the problem started was around the Deborphan or GtkOrphan part.
When I try to run update/upgrade via terminal, I get the message in the first pic. When I try to access Synaptic via GUI, I get the message in the second pic.