Are you upgrading with aptitude?
I got the same issue upgrading because a trigger was activated while
upgrading python2.6/python2.6-minimal; the python2.6 updates were moving
shutil across packages.
python2.6 correctly depends on python2.6-minimal (= ${binary:Version}),
yet python2.6 was
** Attachment added: AptOrdering.txt
http://launchpadlibrarian.net/51656735/AptOrdering.txt
** Attachment added: Dependencies.txt
http://launchpadlibrarian.net/51656736/Dependencies.txt
** Attachment added: Df.txt
http://launchpadlibrarian.net/51656737/Df.txt
** Attachment added: