The following packages will be REMOVED:
openjdk-7-jre openjdk-7-jre-headless tzdata-java
The following packages will be upgraded:
tzdata
1 upgraded, 0 newly installed, 3 to remove and 15 not upgraded.
Need to get 174 kB of archives.
After this operation, 56.9 MB disk space will be freed.
I got around the issue by placing tzdata on hold, dist-upgrading, and then unheld tzdata.