La solution consiste à installer le paquet debian-archive-keyring. Ce paquet a été signé avec l'ancienne clef présente sur le système, on peut donc vérifier qu'il s'agit d'un bon paquet :) .
# apt-get install debian-archive-keyring

Voici les messages qui s'affichent :
# apt-get install debian-archive-keyring
Reading package lists... Done
Building dependency tree... Done
The following NEW packages will be installed:
  debian-archive-keyring
0 upgraded, 1 newly installed, 0 to remove and 133 not upgraded.
Need to get 6768B of archives.
After unpacking 53.2kB of additional disk space will be used.
Get:1 http://ftp.fr.debian.org etch/main debian-archive-keyring 2006.11.22 [6768B]
Fetched 6768B in 0s (24.3kB/s)
Selecting previously deselected package debian-archive-keyring.
(Reading database ... 24202 files and directories currently installed.)
Unpacking debian-archive-keyring (from .../debian-archive-keyring_2006.11.22_all.deb) ...
Setting up debian-archive-keyring (2006.11.22) ...
gpg: keyring `/etc/apt/secring.gpg' created
gpg: /etc/apt/trustdb.gpg: trustdb created
gpg: key 1DB114E0: public key "Debian Archive Automatic Signing Key (2004) <ftpmaster@debian.org>" imported
gpg: key 4F368D5D: "Debian Archive Automatic Signing Key (2005) <ftpmaster@debian.org>" not changed
gpg: key B5F5BBED: public key "Debian AMD64 Archive Key <debian-amd64@lists.debian.org>" imported
gpg: key 2D230C5F: "Debian Archive Automatic Signing Key (2006) <ftpmaster@debian.org>" not changed
gpg: key 6070D3A1: public key "Debian Archive Automatic Signing Key (4.0/etch) <ftpmaster@debian.org>" imported
gpg: Total number processed: 5
gpg:               imported: 3  (RSA: 1)
gpg:              unchanged: 2
gpg: no ultimately trusted keys found


On voit qu'on a ajouter des clefs à notre trousseau, mais ce n'est pas un problème, secure apt a bien vérifié que le paquet est officiel.