First of all, let me say that removing python can lead to many fundamental commands not work anymore. So I don't known if what follow will work.
Secondly, I assume that the package names couldn't be found error you have, derives from a mispelled name on the command line, or from a package installed locally and not available in repositories.
Then, to obtain a log of removed packages, relatively to the last dpkg log available (I don't think you need to take into account older logs):
awk '$3 == "remove" { print $1, $2, $4 }' /var/log/dpkg.log | tee list
Then edit the list file created in the current directory, and only leave lines relative to packages you want to reinstall, based on timestamp of the line. Say you save the modified file to list-mod.
To reinstall that packages, use the following command:
sudo apt-get --simulate install $(awk '{ print $3 }' list-mod)
I inserted the --simulate option to see what the command would do. If it is all ok, do the command again with that option removed.
If the command say some packages cannot be found, simply remove them from list-mod and try again.
Best Answer
PackageKit allows you to search for applications by mime-type. Sadly, the Ubuntu devs haven't put much effort into integrating PackageKit with Ubuntu by default, but it still works surprisingly well.
First, make sure you've installed the graphical toolkit for PackageKit, gnome-packagekit-tools
.
Then, run
gpk-install-mime-typeon the command line, followed by a mime-type. For example:Screenshots: