I find the MintMenu to be just fine. If you want to delete a program and do completely open terminal and run:
sudo apt-get remove --purge <app>
Cleans it from the system.
If you have not done so, go to terminal and type:
sudo gedit /etc/apt/sources.list
Uncomment the romeo repo line, save and close. Next:
sudo apt-get update; sudo apt-get upgrade
When it finishes installing, restart.
You will like the new mintmenu very much.
@sunny rabbiera: tried USP. No comparison. Heavy, large, and missing functionality, such as file access. You couldn't pay me to use it! My two cents, only.
edit: You can try Gimmie. It is in the repo. Don't care to double-click an app to start though. But it may be your cup of tea.
Peace, and Linux Mint!