I hope the bug title is not too confusing… please retitle once you
understand the problem, if you have a better text than me.

I’ve got the following issue on a wheezy/amd64 system, in which we
have, for historical reasons, also our lenny repository included.

The system was, just now, run through:
# apt-get update
# apt-get --purge dist-upgrade
# apt-get --purge autoremove

Currently, openjdk-7 on wheezy is still at -1, but I backported
the -3 upload from sid to lenny already and put it into our local
repository (relying on doko to do the wheezy part as he did before),
leading to the following situation:

root@activity-ci:~ # apt-cache policy openjdk-7-jre-headless
openjdk-7-jre-headless:
  Installed: 7u75-2.5.4-1~deb7u1
  Candidate: 7u75-2.5.4-3~bpo50+1
  Version table:
     7u75-2.5.4-3~bpo50+1 0
        500 http://debs.tarent.de/ lenny/tarent amd64 Packages
 *** 7u75-2.5.4-1~deb7u1 0
        500 http://mirror.lan.tarent.de/debian-security/ wheezy/updates/main amd64 Packages
        500 http://security.eu.debian.org/debian-security/ wheezy/updates/main amd64 Packages
        100 /var/lib/dpkg/status
     7u3-2.1.7-1 0
        500 http://mirror.lan.tarent.de/debian/ wheezy/main amd64 Packages

For as long as 7u75-2.5.4-3~deb7u1 is not uploaded, this situation
will persist. I’m attaching the dpkg status file. More information
you will need to debug this is:

root@activity-ci:~ # apt-cache show openjdk-7-jre-headless=7u75-2.5.4-3~bpo50+1
Package: openjdk-7-jre-headless
Source: openjdk-7
Version: 7u75-2.5.4-3~bpo50+1
Architecture: amd64
Maintainer: OpenJDK Team <openjdk@lists.launchpad.net>
Installed-Size: 56860
Depends: tzdata-java, java-common (>= 0.28), libcups2 (>= 1.3.8), liblcms1, libjpeg62, libnss3-1d (>= 3.12.3), libc6 (>= 2.7-1), libfontconfig1 (>= 2.4.0), libfreetype6 (>= 2.3.5), libgcc1 (>= 1:4.1.1), libkrb53 (>= 1.6.dfsg.2), libpcsclite1 (>= 1.4.102), libstdc++6 (>= 4.1.1), zlib1g (>= 1:1.1.4)
Suggests: libnss-mdns, sun-java6-fonts, ttf-dejavu-core, ttf-baekmuk | ttf-unfonts | ttf-unfonts-core, ttf-sazanami-gothic | ttf-kochi-gothic, ttf-sazanami-mincho | ttf-kochi-mincho, ttf-arphic-uming, ttf-indic-fonts
Breaks: icedtea-netx (<< 1.4-2)
Replaces: openjdk-7-jre-lib (<< 7u45-2.4.3-1)
Provides: java-runtime-headless, java-virtual-machine, java2-runtime-headless, java5-runtime-headless, java6-runtime-headless, java7-runtime-headless
Filename: dists/lenny/tarent/Pkgs/openjdk-7/openjdk-7-jre-headless_7u75-2.5.4-3~bpo50+1_amd64.deb
Size: 41663310
MD5sum: 400aeec7fdd8e3808af4c8efafb2100c
SHA1: 1a51f941a24ee326c34e49190bd6c947f720c9bb
SHA256: d05db0c2a883e9b6fecc40893347ec5371641c9d931d88a95f307b6718105c06
Section: java
Priority: optional
Homepage: http://openjdk.java.net/
Description: OpenJDK Java runtime, using Hotspot JIT (headless)
 Minimal Java runtime - needed for executing non GUI Java programs,
 using Hotspot JIT.
 .
 The packages are built using the IcedTea build support and patches
 from the IcedTea project.

root@activity-ci:~ # apt-cache policy libkrb53
libkrb53:
  Installed: (none)
  Candidate: (none)
  Version table:

The latter part is expected – OpenJDK depends on libkrb5-3 on
wheezy instead. This means that the “newer” version of the package
gets not installed on wheezy because its dependencies are not
fulfillable. So far, so good; this is the expected behaviour.
(I think I’d not care either way.)

The thing here is: the lenny openjdk-7-* packages *do* bring new
dependencies into the play which the (current, older) wheezy one
did not have; an apt-get dist-upgrade *will* install them, despite
being unable to install the *only* package that depends on them,
leading to a subsequent autoremove to remove these again immediately.
(I saw the behaviour a year or so ago with something else, but now
I have something reproducible and from-my-side-debugged which I can
report.)

root@activity-ci:~ # apt-get --purge dist-upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
Calculating upgrade... Done
The following NEW packages will be installed:
  libjpeg62 liblcms1
The following packages have been kept back:
  openjdk-7-jdk openjdk-7-jre openjdk-7-jre-headless
0 upgraded, 2 newly installed, 0 to remove and 3 not upgraded.
Need to get 0 B/210 kB of archives.
After this operation, 473 kB of additional disk space will be used.
Do you want to continue [Y/n]?
Selecting previously unselected package libjpeg62:amd64.
(Reading database ... 45258 files and directories currently installed.)
Unpacking libjpeg62:amd64 (from .../libjpeg62_6b1-3+deb7u1_amd64.deb) ...
Selecting previously unselected package liblcms1:amd64.
Unpacking liblcms1:amd64 (from .../liblcms1_1.19.dfsg-1.2_amd64.deb) ...
Setting up libjpeg62:amd64 (6b1-3+deb7u1) ...
Setting up liblcms1:amd64 (1.19.dfsg-1.2) ...
root@activity-ci:~ # apt-get --purge autoremove
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be REMOVED:
  libjpeg62* liblcms1*
0 upgraded, 0 newly installed, 2 to remove and 3 not upgraded.
After this operation, 473 kB disk space will be freed.
Do you want to continue [Y/n]?
(Reading database ... 45272 files and directories currently installed.)
Removing libjpeg62:amd64 ...
Removing liblcms1:amd64 ...
Purging configuration files for liblcms1:amd64 ...

There you see it. (As I just d-u and autoremoved the system before,
there is nothing else to disturb this.)

I hope this contains enough information to reproduce the problem.
I think you could even create a small reproducer package with,
e.g. equivs. I have not tried to reproduce the issue on sid, for
now; the OpenJDK situation is specific to only a few of our wheezy
machines, and only a “cosmetic” issue, though it may trouble other
Debian users.