W: There is no public key available for the following key IDs:

На одном из тестов VPS оказался Linux Debian 7.2!

(Это при том что сейчас актуальная версия релиза Debian 8.0, а из 7 ветки — 7.8)

Это конечно меня сразу насторожило.

Делаем сразу

apt-get update

И получаем ошибку — W: There is no public key available for the following key IDs:

Четко!

Для решения проблемы выполняем команды:

apt-get install debian-keyring debian-archive-keyring
apt-key update

После этого обновление

apt-get update

работает