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. dpkg really needs an explicit dependency to ensure that when a later version of dpkg is installed, the latest tar 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.deb worked wonders, because dpkg will look in the path and find the latest tar binary before it finds the older version in the regular bin path.
I hope this helps.