Desinstalar um aplicativo do Adobe Air no Ubuntu é bem fácil. Se você ainda tem o arquivo *.air que você usou na instalação, rode ele de novo. Ao abrir, você vai encontrar uma opção de desinstalação.

Mas, e se não tiver mais o arquivo?

Aí fica um pouco mais chato, mas não é complicado. Abra um terminal, e, levando em conta que você instala os aplicativos em /opt, rode o seguinte comando:

sudo dpkg -S /opt/*

Você vai receber de volta uma saída parecida com esta:

adobeair1.0: /opt/Adobe AIR
aremysitesup.69b7a8452702d1f67d8296235c63829bf97d6c7b.1: /opt/aremysitesup
crossover-pro: /opt/cxoffice
app.destroytwitter.23ca2f9b070e2fb8c4472f982f88b1a471f11ae2.1: /opt/DestroyTwitter
net.tw.air.shrinkomatic.7c34f9ba9fad6689faabbe85f1f5b46ba5a32de5.1: /opt/Shrink-O-Matic
de.trakkboard.64285363fdea0945045b9d7bd95b36bcb7421cc7.1: /opt/Trakkboard
tweetdeckfast.fff259dc0ce2657847bbb4aff0e62062efc56543.1: /opt/TweetDeck
vimeo.duplo.3e2f2984357e7a95ae95c69ef2c5c14640284048.1: /opt/Vimeo Uploader

Neste caso, os aplicativos que foram instalados com o Adobe Air tem antes do diretório, um código grande terminado com .1. Para desinstalar o ShrinkOMatic, por exemplo, você precisa do seguinte comando:

sudo dpkg -P net.tw.air.shrinkomatic.7c34f9ba9fad6689faabbe85f1f5b46ba5a32de5.1

Você vai receber uma saída parecida com esta:

(Lendo banco de dados ... 312604 arquivos e diretórios atualmente instalados).
Removendo net.tw.air.shrinkomatic.7c34f9ba9fad6689faabbe85f1f5b46ba5a32de5.1 ...

E é só. Fácil, não?!