This error occurs from time to time on some of our Debian boxes, extremely simple to fix just requires the process of obtaining the authenticity of the packages.

After running apt-get update you will see a series of keys that the system does not trust, simply make a note and substitute the key value in the following command:

gpg --keyserver pgpkeys.mit.edu --recv-key 841D6D8DFE3F8BB2
gpg -a --export 841D6D8DFE3F8BB2 | apt-key add -

Now run apt-get update again and continue to update the installed packages as you would do normally:

apt-get update

One further note, we run several XenServer instances and spotted that we got the following error:

gpg: no valid OpenPGP data found.

The only solution we found was written by Steve Glendinning suggesting:

wget -q http://updates.vmd.citrix.com/XenServer/5.5.0/GPG-KEY -O- | apt-key add -

Which worked a treat and the apt-get update reported no faults.