Al final encontre la solucion en Google :PTe vas a la carpeta /var/lib/dpkg/info y borras todos los archivos que se refieren al paquete en cuestion, que en mi caso han sido los que empiezan por adobe (son cuatro).
Despues ejecutamos en una consola de root dpkg -r --force-remove-reinstreq adobe-flashplugin . Y ya esta solucionado.