abra um terminal e digite sudo apt-get remove o puddletag se você o instalou como um arquivo deb usando o gdebi então abra o arquivo deb com o gdebi e ele terá a opção de reinstalá-lo ou removê-lo. ou você também pode procurar no synaptic para ver se ele está lá, se ele não aparecer no centro do softare! espero que isso ajude