Isso foi corrigido na próxima versão do Ubuntu do Natty: link
Aqueles que usam uma versão mais antiga precisam editar ppa.py:
sudo gedit /usr/lib/python2.6/dist-packages/softwareproperties/ppa.py
Onde diz:
keyserver.ubuntu.com
mude para:
hkp://keyserver.ubuntu.com:80
Salve, saia e espere que seja bom.