I've had the same problem on squeeze, but this answer should be applicable to older versions as well. Simply change tzdata's version numbers as needed.
First, do an apt-cache showpkg tzdata:
raphael@hydra:~$ apt-cache showpkg tzdata-java
Package: tzdata-java
Versions:
(snip)
Dependencies:
2011k-0squeeze1 - tzdata (5 2011k-0squeeze1)
Provides:
2011k-0squeeze1 -
Reverse Provides:
As you can see, it depends on tzdata (2011k-0squeeze1) - at least on my system. Now let's take a look at tzdata:
raphael@hydra:~$ apt-cache showpkg tzdata
Package: tzdata
Versions:
(snip)
Provides:
2011l-0squeeze1 - tzdata-squeeze
2011k-0squeeze1 - tzdata-squeeze
Reverse Provides:
Oh, look, I've already got the old 2011k and the new 2011l installed. I'm not sure why it doesn't work, however, we can force apt-get to downgradetzdata which, as we'll see, is going to create a tear in spacetime:
raphael@hydra:~$ sudo apt-get install tzdata=2011k-0squeeze1
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be DOWNGRADED:
tzdata
0 upgraded, 0 newly installed, 1 downgraded, 0 to remove and 0 not upgraded.
Need to get 630 kB of archives.
After this operation, 0 B of additional disk space will be used.
Do you want to continue [Y/n]? y
(snip)
dpkg: warning: downgrading tzdata from 2011l-0squeeze1 to 2011k-0squeeze1.
(Reading database ... 167509 files and directories currently installed.)
Preparing to replace tzdata 2011l-0squeeze1 (using .../tzdata_2011k-0squeeze1_all.deb) ...
Unpacking replacement tzdata ...
Setting up tzdata (2011k-0squeeze1) ...
(snip)
Now you might think, hey, if I run the update manager it will install the newer tzdata! But no, it won't:
raphael@hydra:~$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
(Schrödinger's package strikes back.)
Lo and behold, now I can install tzdata-java:
raphael@hydra:~$ sudo apt-get install tzdata-java
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
tzdata-java
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 143 kB of archives.
(snip)