apt-get shows important packages as “no longer required”

Definitely nothing is broken. When a package is installed, there are often other packages that it depends on. These will be automatically installed by apt-get. It used to be that you would be forced to use a separate program if you wanted keep track of these packages and remove them if you ever removed the original program that you installed.

Now apt implements an Auto-Installed state flag to keep track of these packages that were never installed explicitly. When you uninstall a package you can add the --auto-remove option to additionally remove any packages which have their Auto-Installed flag set and no longer have any packages which depend on it being there (a package may also be kept if another suggests or recommends it depending on the value of the APT::AutoRemove::RecommendsImportant and APT::AutoRemove::SuggestsImportant configuration options).

I would have a look at the list of packages and decide if they are worth keeping, sometimes packages which you may wan to keep are marked Auto-Installed by default. You can get information on what the various packages do by doing apt-cache show package_name. If you decide to keep some, you can use apt-mark manual followed by the names of the packages you want to keep.

Note that usually you would want to have library packages (most packages beginning with lib) marked as Auto-Installed since there are few reasons to have these packages installed on their own - other programs usually require other libraries to run, but they are little use on their own. Even if you are compiling software against the library to need the development package (ending in -dev) which depends on the library itself, so no need to explicitly install the library.

Also using aptitude, you can do aptitude unmarkauto from the command line or change within the curses interface. Within the package lists in the interface, all automatically installed packages have an A next to them. You can change this state by using m to mark an auto installed package as manual and M to mark as manual again (also l to open a search dialog and Enter to view package details).

to mark all these packages so that they are important and not to be removed, do this:

apt-mark showauto | xargs sudo apt-get -y install

basically by telling apt to install a program you are telling it that you want it to remain on the system permanently.