la ricerca l'hai fatta da root ?

prova a dare in una console, come root, i comandi

updatedb

locate kino

which kino

a me ad esempio

[giorgio@mandriva_2007_spring ~]$ which kino
/usr/bin/kino
[giorgio@mandriva_2007_spring ~]$

ma nelle mini distro, sovente il sistema, e quindi le posizioni dei vari file, possono essere diverse.

A meno che non te l'abbia installato correttamente.