A few days ago launchy version 2.1.1 was released for linux, and even though I have been using gnome-do for a few months now, I must admit, that Launchy is alot better. The download page on sourceforge has a *.deb installer that works without a hitch on Elyssa, and even puts an icon in "Accessories", not that you'd ever access it without the hotkey.
I really recommend to
1. Add it to the software portal at least
2. Make this the default in Linux Mint rather than Gnome-do.