WARNING: The following packages cannot be authenticated!

This is a Debian warning after an:

sudo apt-get update
sudo apt-get upgrade

After going through many sources around the correct solution turned out to be be:

sudo rm -r /var/lib/apt/lists
sudo mkdir -p /var/lib/apt/lists/partial
sudo apt-get update

Now you should be able to run the upgrade.

Source: http://doc.ubuntu-fr.org/probleme_apt#erreur_gpg