It looks like the conflicting packages to be removed in your second quote are almost exclusively from the gnome
group/metapackage or are from gnome's family of dependencies. Are you running a backport or custom build of a more modern version of Gnome (i.e. >3.4)? Or maybe some other backports? That can sometimes create these kinds of issues when the backport has newer dependencies which conflict with the "stable" dependencies. If that's not the issue, I assume you've tried the obvious things like updating your package lists using "upgrade" or "dist-upgrade"?
FWIW, I just did an install of Debian Jessie/testing 64-bit on my server last week, and I had no problems installing the dependencies for both gnome and mc. I'm not suggesting a re-install as a solution for you necessarily, but rather to note that with fully updated package lists and dependencies I was able to install the referenced lib, and everything was able to coexist with no problems on a 64-bit Debian build (albeit not Wheezy).
Maybe somebody who is running Wheezy with Gnome can weigh in?