Иногда после добавления нового репозитория в Ubuntu при выполнении команды aptitude update могут выскакивать подобные ошибки:

W: GPG error: http://packages.linuxmint.com isadora
Release: The following signatures couldn't be verified because the
public key is not available: NO_PUBKEY 3EE67F3D0FF405B2

Да, это жалуется на отсутствие ключа репозиторий, который я подключала для установки MintMenu. И только сейчас я решила разобраться с этой ошибкой.

На самом деле, многие репозитории защищены от подмены пакетов в них посредством цифровых подписей. Пользовательский компьютер должен содержать открытый ключ для сторонних репозиториев, чтобы они могли считаться доверенными.
Чаще всего там же, где описывается подключение репозитория и даётся его адрес, рядом даётся и вся необходимая информация для добавления в систему открытого ключа.

Например, при добавлении репозиториев Medibuntu ключ добавляется посредством установки специального пакета прямо из только что подключенного репозитория. На специальной странице дана команда, делающая всё разом, но её можно и разделить на этапы. Так вот в предпоследнем этапе там как раз устанавливается пакет medibuntu-keyring, который и является открытым ключом для добавленного ранее репозитория.

Ещё при добавлении репозитория c launchpad ключи добавляются сразу автоматически, но при этом должна использоваться команда add-apt repository … (точная команда даётся на странице каждого пакета).

А ещё довольно распространён случай, когда на странице даётся адрес репозитория, который надо добавить в /etc/apt/sources.list, а затем адрес открытого ключа. Ну например, как на странице wakoopa-tracker.
Первым пунктом там идёт — прописать строку deb http://apt.wakoopa.com all main в файл /etc/apt/sources.list, а вторым — скачать ключ http://apt.wakoopa.com/pubkey.txt и импортировать.
Скачать можно так:

wget http://apt.wakoopa.com/pubkey.txt

(при этом ключ скачается в домашнюю директорию текущего пользователя), можно скачать и другим удобным вам способом, конечно. А импортировать можно следующей командой:

sudo apt-key add pubkey.txt

При этом, конечно, pubkey.txt нужно заменить на имя файла, который скачали вы в конкретном случае (если вы добавляете ключ для другого репозитория), ну и скачан файл должен в ту папку из которой выполняется команда (ну или вам следует перейти в ту папку).

Между прочим, добавление ключа (как и добавление репозитория) возможно выполнять и в графическом интерфейсе. В частности в программе Synaptic нужно открыть через меню Settings — Preferences окно Software Sources и можно добавить репозитории во вкладке Other Software, а ключи во вкладке Authentication. Это окно можно открыть и отдельно через System — Administration, либо командой gksu software-properties-gtk (или kdesudo software-properties-kde для KDE соответственно)

Это были самые простые случаи, когда сам ключ или способы его добавления даются сразу. А в том случае, когда репозиторий уже добавлен и ключ неизвестно где или просто искать его не хочется, можно добавить ключ, используя его идентификатор. Это тот набор символов, что выдаётся в тексте ошибки (о которой речь была в самом начале).
То есть, чтобы добавить недостающий ключ от стороннего репозитория, нужен этот самый идентификатор и адрес специального защищённого сервера с ключами, откуда его и надо импортировать. А импорт ключа производится командой.
Впрочем вариантов несколько. Это, пожалуй, самый простой:

sudo apt-key adv --recv-keys --keyserver keyserver.ubuntu.com 1234567890ABCDEF

А этот в два приёма:

gpg --keyserver keyserver.ubuntu.com --recv 1234567890ABCDEF
gpg --export --armor 1234567890ABCDEF | sudo apt-key add -

В этих примерах 1234567890ABCDEF не забыть заменить на свой идентификатор ключа (который выдаётся в тексте ошибки), а вместо keyserver.ubuntu.com можно попробовать subkeys.pgp.net (скорее всего, существуют ещё подобные публичные сервера, но пока я нашла только эти).

Ещё можно попробовать импортировать все недостающие ключи командой:

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

В других дистрибутивах, насколько я успела понять, принцип тот же, но сервера открытых ключей и способы их импортирования в систему могут отличаться.