I've just had exactly this problem. As Gilles suggested, upgrading tar is the answer but (surprise surprise) tar can't be upgraded in the usual way because dpkg requires version 1.23 or later before it'll unpack and install the latest tar deb. dpkgreally needs an explicit dependency to ensure that when a later version ofdpkgis installed, the latesttar` version goes on first, but I guess it's a risk with combining different testing and unstable releases in unsupported ways. It's still undesirable and this seems an unfortunate way to cripple a system.
My first idea was to look for the latest binary of tar at the GNU project, but unfortunately they only have source downloads, which aren't helpful if (like me) you don't have the various compiling tools installed.
If you download the latest tar binary .deb to match your system from packages.debian.org and drop it into a temporary place somewhere (just to be tidy), you should be able to get inside it with the ar command, e.g. ar x tar_1.26-2_amd64.deb in my case. Then unpack the resulting data.tar.gz file with a command like tar zxvf data.tar.gz, using your existing earlier version of tar, which should work as long as you don't try and do anything silly like use a --warning parameter that won't be available until version 1.23. :) This will then let you get at the tar binary, which (within the data.tar.gz file) was probably at bin/tar. Having done this, I added the path for that binary to the front the PATH variable in my shell, which in my bash shell could be done with the command export PATH=/root/temp/bin:$PATH, but adjust the path to fit wherever the new tar binary is now sitting. After that, running a regular dpkg --install tar_1.26-2_amd64.debworked wonders, becausedpkgwill look in the path and find the latesttarbinary before it finds the older version in the regularbin` path.
I hope this helps.
