This seems to be happening only on some machines. May be an apt-cacher bug? Still investigating.
root@sql:/opt# aptitude install openjdk-6-jre-headless
The following NEW packages will be installed:
ca-certificates-java{a} dbus{a} java-common{a} libavahi-client3{a} libavahi-common-data{a}
libavahi-common3{a} libcups2{a} libdbus-1-3{a} liblcms1{a} libnspr4-0d{a} libnss3-1d{a}
openjdk-6-jre-headless openjdk-6-jre-lib{a} tzdata-java{ab}
0 packages upgraded, 14 newly installed, 0 to remove and 0 not upgraded.
Need to get 33.9 MB of archives. After unpacking 93.6 MB will be used.
The following packages have unmet dependencies:
tzdata-java: Depends: tzdata (= 2012c-0squeeze1) but 2012g-0squeeze1 is installed.
The following actions will resolve these dependencies:
Keep the following packages at their current version:
1) ca-certificates-java [Not Installed]
2) openjdk-6-jre-headless [Not Installed]
3) openjdk-6-jre-lib [Not Installed]
4) tzdata-java [Not Installed]
Accept this solution? [Y/n/q/?] q
Abandoning all efforts to resolve these dependencies.
Abort.
root@sql:/opt# aptitude install tzdata-java
The following NEW packages will be installed:
tzdata-java{b}
0 packages upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 148 kB of archives. After unpacking 1,987 kB will be used.
The following packages have unmet dependencies:
tzdata-java: Depends: tzdata (= 2012c-0squeeze1) but 2012g-0squeeze1 is installed.
The following actions will resolve these dependencies:
Keep the following packages at their current version:
1) tzdata-java [Not Installed]
Accept this solution? [Y/n/q/?] n
The following actions will resolve these dependencies:
Downgrade the following packages:
1) tzdata [2012g-0squeeze1 (now) -> 2012c-0squeeze1 (stable)]
Accept this solution? [Y/n/q/?] Y
The following packages will be DOWNGRADED:
tzdata
The following NEW packages will be installed:
tzdata-java
0 packages upgraded, 1 newly installed, 1 downgraded, 0 to remove and 0 not upgraded.
Need to get 884 kB of archives. After unpacking 2,281 kB will be used.
Do you want to continue? [Y/n/?] Y
root@sql:/opt# aptitude install openjdk-6-jre-headless
The following NEW packages will be installed:
ca-certificates-java{a} dbus{a} java-common{a} libavahi-client3{a} libavahi-common-data{a}
libavahi-common3{a} libcups2{a} libdbus-1-3{a} liblcms1{a} libnspr4-0d{a} libnss3-1d{a}
openjdk-6-jre-headless openjdk-6-jre-lib{a}
0 packages upgraded, 13 newly installed, 0 to remove and 0 not upgraded.
Need to get 33.8 MB of archives. After unpacking 91.6 MB will be used.
Do you want to continue? [Y/n/?] Y
Manually changing the package version for tzdata as suggested online in some places WILL break apt at some point. Not a bright idea.