I had a problem due to Windows not having a package manager. I had emacs and RCS installed, and it worked fine. Then I installed a CVS package that included the programs it needed, including RCS programs. Its version didn't work with emacs. If there were a package manager I would have been warned about the conflict.

I've been using Debian for years, and Ubuntu recently, but I had to look up autoremove; I've never used that apt-get feature. I have used autoclean, which is benign. It does sound like there are problems with autoremove that should be fixed, but for now why not just avoid that feature?