The “Show Info” service could not be used because the application could not be found
Sounds like removing/un-installing that app damaged something in Finder. Which is an integral part of the OS (bear with me here...) Usually when you are having OS problems I recommend installing the latest update via a combo updater downloaded directly from support.apple.com.

Combo updaters have all of the patches required for all versions of the OS including hardware variations. When you download it from the App Store you get only the code necessary for your particular Mac. So combo updaters are more complete.

El Capitan does not seem to have a Combo Updater as this is all I could find. If you have Yosemite this would be your Combo Updater. If you look at both pages one is called a combo updater and one is not.

Speculating on what Apple is doing (or going to do) is both fruitless and (sometimes) fun. So why this is happening, who knows.

Since there is not a Combo Updater for El Cap (assuming that is what you have) I would download that updater and apply it to your system. If you have Yosemite, the second link. If you have an earlier version, well just google the version you say along with "combo updater" and the first link is usually the Apple download page.

Failing that sometimes just reinstalling the OS and then applying any updates is the way to go. Doing that will rarely wipe any of your data, but do back-up first, just to be safe.