There are few reasons why I believe upgrade does not bring in entirely new packages by default when dependencies are changed.
1. The man page of apt-get says the following upgrade upgrade is used to install the newest versions of all packages currently installed on the system from the sources enumerated in /etc/apt/sources.list. Packages currently installed with new versions available are retrieved and upgraded; under no circumstances are currently installed packages removed, or packages not already installed retrieved and installed. New versions of currently installed packages that cannot be upgraded without changing the install status of another package will be left at their current version. An update must be performed first so that apt-get knows that new versions of packages are available. dist-upgrade dist-upgrade in addition to performing the function of upgrade, also intelligently handles changing dependencies with new versions of packages; apt-get has a "smart" conflict resolution system, and it will attempt to upgrade the most important packages at the expense of less important ones if necessary. The dist-upgrade command may therefore remove some packages. The /etc/apt/sources.list file contains a list of locations from which to retrieve desired package files. See also apt_preferences(5) for a mechanism for overriding the general settings for individual packages. 2. apt-get upgrade keeps the package back, but all of the following succeed to upgrade the package apt-get --with-new-pkgs upgrade apt-get install libopenhpi-dev apt-get dist-upgrade (If the openhpi was already installed then there is no problem at all. Usually it is always installed, that may be the reason this bug was not caught for decades) 3. https://debian-administration.org/article/69/Some_upgrades_show_packages_being_kept_back https://askubuntu.com/questions/194651/why-use-apt-get-upgrade-instead-of-apt-get-dist-upgrade#226213 The above pages are old, but relevant. There are many more web pages that I do not remember that also point to the same thing (spent many hours/days on it). If the dependencies are changed and that needs new packages that are not already installed, then do not bring them in. Keep those packages back. So apt-get is little conservative when upgrade is specified in the command line and leaves the decision to the user. But when user is little more clear it brings in the new packages. Regards Mohan