Бывает, что при обновлении Убунта жалуется, что с ключами что-то не в порядке.

Пробуем импортировать все недостающие ключи репозиториев (спасибо wiki с офсайта):

sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com `sudo aptitude update 2>&1 | grep -o '[0-9A-Z]\{16\}$' | xargs`

Затем, разумеется,

sudo apt-get update

и

sudo apt-get upgrade

Радуемся, пьём коньяк.