On my feisty machines I regularly get
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
f-spot libgnomecupsui1.0-1c2a libwpd8c2a libxmlsec1 wamerican evolution-webcal ekiga openoffice.org-gnome gimp-print ttf-devanagari-fonts libjaxp1.2-java pnm2ppa linux-headers-2.6.20-6 gthumb openoffice.org-core gnome-nettool
libgphoto2-port0 openoffice.org-style-default libneon26 cdparanoia openoffice.org-impress ubuntu-docs ttf-punjabi-fonts wvdial xsane ttf-indic-fonts intltool-debian libdjvulibre15 libwmf0.2-7 tangerine-icon-theme libicu36
openoffice.org-draw libstlport5.1 ttf-thai-tlwg ttf-kochi-mincho libxmlsec1-openssl doc-base brltty-x11 avahi-daemon vnc-common ttf-mgopen openoffice.org-java-common openoffice.org-gtk libwvstreams4.2-base libsane esound
ttf-kannada-fonts ttf-gentium rhythmbox bluez-cups readahead libieee1284-3 libstlport4.6c2 openoffice.org-style-industrial screen bc acpi dc libxmlsec1-nss po-debconf python-virtkey gnome2-user-guide whois scim-modules-socket
powernowd openoffice.org-l10n-common scim libgpod0 libgpod1 libscim8c2a ttf-lao usplash-theme-ubuntu libgphoto2-2 libmdbtools ttf-kochi-gothic libnss-mdns tango-icon-theme-common libpoppler1-glib tango-icon-theme foomatic-db-hpijs
scim-gtk2-immodule libgutenprintui2-1 bluez-utils gettext diveintopython libmusicbrainz4c2a ttf-gujarati-fonts xvncviewer bsh gnome-volume-manager openoffice.org-evolution libkpathsea4 openoffice.org-math screensaver-default-images
openoffice.org-common ttf-telugu-fonts libjaxp1.3-java gnome-spell bug-buddy ttf-tamil-fonts libgutenprint2 ttf-opensymbol avahi-autoipd vino libjline-java gnome-keyring-manager cupsys-driver-gutenprint libxerces2-java
libmono-sqlite2.0-cil evince ttf-arphic-uming ttf-malayalam-fonts openoffice.org-thesaurus-en-us landscape-client contact-lookup-applet libxalan2-java linux-headers-2.6.20-6-generic xcursor-themes gimp foo2zjs xsane-common
ttf-arphic-ukai libgimp2.0 libwvstreams4.2-extras libdaemon0 libxplc0.3.13 ttf-oriya-fonts liboobs-1-2 libgucharmap5 onboard ttf-baekmuk libmyspell3c2 openoffice.org-l10n-en-gb libhsqldb-java libopal-2.2.0 gconf-editor
gnome-system-tools ttf-arabeyes libuniconf4.2 libservlet2.3-java openoffice.org-base openoffice.org-l10n-en-za wbritish hotkey-setup mozilla-firefox-locale-en-gb openoffice.org-calc ttf-bengali-fonts gimp-data gnome-mount min12xxw
libavahi-core4 libavahi-core5 freeglut3 libsndfile1 make bluez-pin example-content gimp-python serpentine gnome-cups-manager ssh-askpass-gnome sound-juicer lftp
Use 'apt-get autoremove' to remove them.
I don't know about the library, but some of these (like lftp) I specifically asked for, and some of the others (gimp and make) seem like very strange things to autoremove.
I have not been brave enough to run it and see what happens...
I've just reinstalled and have a similar situation. Basically I just came up from alternate and installed ubuntu-desktop