I ran into various issues with not totally "cleaned" systems especially after upgrades as asked in this question.
I hope this "more thorough cleaning" might help more than just me.
In my case I had a Server that started on 12.04 and went through various ppa's and ups/downs and experiments - after upgrading to 14.04 I fixed stuff the hard way - but after my upgrade to 16.04 this week a lot of things didn't work properly (like input on X11 at all).
To clean up and get rid of a lot without really reinstalling the machine I did the following:
First I wanted to get rid of old ppas, especially in case they still would overwrite even the newer packages
Other than just apt-add-repository -r this also tries to revert to the original
See this for more: Difference between "ppa-purge" and "add-apt-repository -r"?
$ ppa-purge "ppaname"
Next I got a list of all "manual" installed packages
$ comm -23 <(apt-mark showmanual | sort -u) <(gzip -dc /var/log/installer/initial-status.gz | sed -n 's/^Package: //p' | sort -u) > manual.txt
Clean up in this file, remove all packages from this list that you would like to keep
$ vim manual.txt
Then set all these packages from manual to auto installed
$ while read p; do sudo apt-mark auto ${p}; done <manual-to-remove.txt
This put a lot into the next autoremove, all desktops I ever tried I recognized a lot of the experiments I did the last years.
But other than hard removing them I could be sure that everything still needed by dependencies still woudl be fine.
$ sudo apt-get autoremove
If you are really willing to clean up add --purge to the autoremove - this will remove all conffiles that are associated.
Be careful if you are unsure if you want to keep anything.
E voila:
0 upgraded, 0 newly installed, 1359 to remove and 0 not upgraded.
After this operation, 3.810 MB disk space will be freed.
That was a lot of crap :-)
Since these days everything just works (I knew from a test with a live image) I could now cleanly install kubuntu-desktop and was happy again - yay.