En Ubuntu Feisty cada vez que intenten correr aplicaciones no instaladas aparecerá el siguiente mensaje:

wiki@wiki-desktop:~$ amsn
The program ‘amsn’ is currently not installed. You can install it by typing:
sudo apt-get install amsn
Make sure you have the ‘universe’ component enabled
bash: amsn: orden no encontrada

Cabe aclarar que solo funciona desde la linea de comandos.
Para instalar esta novedad sudo apt-get install command-not-found