Na verdade, eu tive que fazer isso há um tempo (alguns anos atrás, então desculpe os comandos não perfeitos) e é isso que eu fiz.
Primeiro:
dpkg --get-selections > installed.txt
Então, aconteceu de eu ter uma nova instalação em volta da qual fiz a mesma coisa. Se você não tiver um, provavelmente poderá encontrar uma lista em algum lugar para sua distribuição. Então:
sdiff [your install list] [clean install list] --suppress-common-lines > differences.txt
sdiff [clean install list] [differences] --suppress-common-lines > remove.txt
O segundo sdiff é permitir pacotes padrão que você possa ter removido da sua instalação. Só queria evitar mais erros então necessários. A próxima parte é realmente qualquer que seja o seu método favorito para pesquisa e substituição, eu gosto do vim e é isso que eu usei.
:%s/install//g
Isso ocorre porque o dkpg deixa a palavra de instalação após cada pacote na lista e não queremos isso. Também executei mais alguns comandos no vim para remover o excesso de espaço em branco e substituir as quebras de linha por espaços, apenas para torná-lo um pouco mais limpo. Você então executa este arquivo através do apt-get remove (adicione --pur se quiser).
Se você quiser ser mais completo, você pode usar limpadores diferentes para se livrar da porcaria, e também executar a comparação de forma diferente para que você possa adicionar os pacotes de volta que você pode ter removido [da lista de pacotes padrão].
Tudo somado, depois que eu fiz tudo o que eu decidi, não valia a pena o esforço em comparação com a relativa facilidade de reinstalar o Ubuntu.