Бывает, что при обновлении Убунта жалуется, что с ключами что-то не в порядке.
Пробуем импортировать все недостающие ключи репозиториев (спасибо 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
Радуемся, пьём коньяк.