Da sua mensagem de erro, parece que você adicionou este PPA , que não contém nenhum pacote. Isso é o que está causando esses problemas. Para corrigir isso, vá para Aplicativos - > Centro de Software - > Editar - > Fontes de software - > Outro Software e desmarque estas entradas:
deb http://ppa.launchpad.net/ubuntu-advertising/ppa/ubuntu maverick main
deb-src http://ppa.launchpad.net/ubuntu-advertising/ppa/ubuntu maverick main