I liked this solution, re-download the missing keys from the Ubuntu key server.

For Ubuntu

• UBUNTU: Fixing GPG Keys in UBUNTU

In my case

 Reading package lists... Done  
 W: GPG error: http://ppa.launchpad.net precise 
 Release: The following signatures couldn't be verified because the public key is not available: 
 NO_PUBKEY 2EA8F35793D8809A

Here is the command to add the missing key mentioned in the error message.

sudo apt-key adv --keyserver ha.pool.sks-keyservers.net --recv-keys 2EA8F35793D8809A

So I take the missing key 2EA8F35793D8809A and ask the keyserver.ubuntu.com to added it to the list of keys I have in apt.

For linux mint
Your key server is slightly different keyserver.linuxmint.com

sudo apt-key adv --recv-key --keyserver keyserver.linuxmint.com "missing key"

Alternative key servers to try
keyserver.ubuntu.com

There is a software called as Y PPA manager It can help fix GPG keys errors.
Y PPA manager

To install -

sudo add-apt-repository ppa:webupd8team/y-ppa-manager  
sudo apt-get update  
sudo apt-get install y-ppa-manager    

Once you install it start it ,then go to advance and select "import all missing GPG keys"

The automatic download using apt-key adv --recv-keys may not work behind a firewall.

In this case, open the webpage of Ubuntu Key Server in your web browser and search for the string 0x<hexadecimal code of your missing key>.

Open the link in the pub section. Save the key contents (from -----BEGIN PGP PUBLIC KEY BLOCK----- to -----END PGP PUBLIC KEY BLOCK-----) as a file.

Then run:

sudo apt-key add <file-with-saved-key>

Source: http://opensourceforgeeks.blogspot.in/2013/04/w-gpg-error-httpppalaunchpadnet-precise.html

first enter the following command in the terminal

 sudo rm /var/lib/apt/lists/* -vf

then update your system by entering the following command in the terminal

 sudo apt-get update && sudo apt-get upgrade

after this there should be no errors and everything should work fine.

For Ubuntu 12.04 Precise: Permanent solution

to this error message occuring after adding a new repository and updating repository list. This is due to a server which address is no more valid. So just change the address to a good one.

1. Open the file ~/.gnupg/gpg.conf with a text editor.

   In terminal: gedit ~/.gnupg/gpg.conf

2. then, in this file, find the following bold line (116th line) (which should be default as follow):

   [...]
   keyserver hkp://keys.gnupg.net
   # keyserver mailto:[email protected]
   # keyserver ldap://keyserver.pgp.com

3. then add the following bold line, to finally give the following result:

   (add # to the second line as follow to comment out the old address)

   [...]
   keyserver http://keyserver.ubuntu.com
# keyserver hkp://keys.gnupg.net
   # keyserver mailto:[email protected]
   # keyserver ldap://keyserver.pgp.com

4. Save the file and try to update again:

   In terminal: sudo apt-get update

Based on nelaar answer:

sudo apt-get update 2>&1 1>/dev/null | sed -ne 's/.*NO_PUBKEY //p' |
while read key; do
    echo 'Processing key:' "$key"
    sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys "$key"
done

The script dumps all the errors into a temporary file and then loops through them, importing the missing keys.

The Most Easiest Way Is With Y PPA MAnager

sudo add-apt-repository ppa:webupd8team/y-ppa-manager
sudo apt-get update
sudo apt-get install y-ppa-manager 

Open Y PPA Manager From Dash

Enter Your Admin Password

Double Click On Advanced Option

Click Try To Import All Missing GPG Keys

Click Ok To Fix It

What worked for me was to delete the key first and then reinstall. To achieve that I did the following:

[email protected] > ~: sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 630239CC130E1A7FD81A27B140976EAF437D05B5

deleting with

[email protected] > ~: sudo apt-key del 630239CC130E1A7FD81A27B140976EAF437D05B5

Then, re-install by typing

[email protected] > ~: sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 630239CC130E1A7FD81A27B140976EAF437D05B5

I have encountered the same issue, by adding a ppa(ppa:nathandyer/vocal-stable), it broke my repositories. I was guided from the Author of Web Upd8, on how I can try to fix this, here are his steps that worked me.

Backup your .gpg keys, just in case that something goes wrong.

Lets make a folder in which we will house our backup in.

• mkdir ~/gpg-backups

  This backups all files in the /etc/apt/trusted.gpg.d/ folder.

• sudo cp /etc/apt/trusted.gpg.d/*.* ~/gpg-backups/

Now, we will remove all the .gpg keys.

• sudo rm /etc/apt/trusted.gpg.d/

• sudo cp /etc/apt/trustdb.gpg ~/gpg-backups/

• sudo rm /etc/apt/trustdb.gpg

in Software & Updates, on the "Authentication" tab, clicked "Restore Defaults

Install y-ppa manager to import all missing GPG keys

sudo add-apt-repository ppa:webupd8team/y-ppa-manager
sudo apt-get update
sudo apt-get install y-ppa-manager

Reference:

• Try Vocal, A Podcast Manager Designed For elementary OS ~ Web Upd8: Ubuntu / Linux blog#comment-1981323351

I wanted to automatically fix errors like this in a bash script. For anyone interested, this should do the trick:

sudo apt-get update 2> /tmp/keymissing
if [ -f /tmp/keymissing ]
then
    for key in $(grep "NO_PUBKEY" /tmp/keymissing |sed "s/.*NO_PUBKEY //")
        do 
        echo -e "\nProcessing key: $key"
        sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys $key
        sudo apt-get update
    done
    rm /tmp/keymissing
fi