Two very usable and handy launcher tools for Linux. Both are Skinable, configurable, have plugins and are easy to use:
Launchy - cross platform (Mac, Windows and Linux). Linux support seems to be limited to Ubuntu only.
Do - Linux only but supports all the major distros (Ubuntu, Fedora, openSUSE, Arch Linux, Gentoo and Source)