A todos nos ha pasado que alguna vez hemos tenido el problema de que nuestro Ubuntu no pudo validar un update porque las llaves de los repositorios no fueron validadas.
Es por eso que una vez navegando por internet encontré este pequeño archivo que básicamente lo que hace es actualizar el repositorio de llaves, además puedo decir que el 99% de las veces funciona.
Lo primero que tienen que hacer es descargar el archivo en el siguiente link: http://www.megaupload.com/?d=C6GA4JRM.

Posteriormente pongan el archivo idealmente en la carpeta de usuario, y luego de que les arroje el típico problema de que no se puedo actualizar tal aplicación porque no se encontró la llave pública, abren una terminal y escriben sudo ./launchpad-update xxxxx, siendo xxxxx la versión de Ubuntu que tengan (jaunty, etc).

Luego de este proceso el problema tendría que estar solucionado.