Ага, ну, т.е. кандидат один и он из официальной репы.
Тогда apt show mcollective-common думаю покажет, что зависимостей от puppet у него действительно нет.

+

А когда оно хочет снести всё, оно что-то пишет, почему оно хочет это сделать?

Ну, может, про версии что-то?

The following packages will be REMOVED:
 puppet-agent puppetdb puppetdb-termini puppetserver
The following NEW packages will be installed:
 augeas-lenses bind9-host debconf-utils facter geoip-database hiera javascript-common libaugeas0 libbind9-90 libdns100 libgeoip1 libisc95 libisccc90 libisccfg90 libjs-jquery liblwres90 libruby2.1 libyaml-0-2
 mcollective-common puppet puppet-common ruby ruby-augeas ruby-hiera ruby-json ruby-rgen ruby-safe-yaml ruby-selinux ruby-shadow ruby-stomp ruby-systemu ruby2.1 rubygems-integration virt-what

Оно судя по всему из дебиановских реп собралось puppet тянуть

apt-cache policy puppet?

Installed: (none)
 Candidate: 3.7.2-4

root@infra:~# apt-cache policy puppet-agent
puppet-agent:
 Installed: 1.10.0-1jessie
 Candidate: 1.10.0-1jessie

Ну а тут стоит 4.10 групбо говоря

А он как у вас ставился?

У нас по документации) скачиваешь puppetlabs - устанавливаешь - ставишь puppet-agent)

root@infra:~# apt-cache policy puppetserver
puppetserver:
 Installed: 2.7.2-1puppetlabs1
 Candidate: 2.7.2-1puppetlabs1

я бы пересобрала пакет

и почистила зависимости (для теста можно попробовать поставить игнорируя зависимости, и посмотреть, что будет)

Там его пакет puppet-agent ломает:
Breaks: ... mcollective (« 3.0.0)

Таки оно должно сейчас всё притаскиваться при его установке. И притаскивается.

А плагины вы используете самописные какие-то?

Нет

puppet плагин))

А его ставили как?