Someone (Nickname: Salz) on the german debian irc helped solving this problem. Just delete the *.bin files in /var/cache/apt/ -- Florian Sievers