I also experience this problem; after running debdelta-upgrade I use this snippet (all on one line; not elegant) to fix up the files so that apt can find them:
for i in /var/cache/apt/archives/*%*; do sudo mv -n "$i" `perl -e '$ARGV[0] =~ s/%(2b|7e)/chr(hex($1))/ge; print $ARGV[0]' "$i"`; done The affected characters, for me, are %2b (+) and %7e (~).
