Investigando o tópico um pouco mais, descobri que command-not-found estava usando o script /usr/lib/python2.7/dist-packages/CommandNotFound/CommandNotFound.py , que contém a seguinte linha:
self.user_can_sudo = grp.getgrnam("sudo")[2] in posix.getgroups() or grp.getgrnam("admin")[2] in posix.getgroups()
Então, basicamente, todos os grupos sudo ou admin serão considerados como administradores. Uma das máquinas foi configurada para usar o grupo wheel , portanto, visudo mostraria:
%wheel ALL=(ALL) ALL
No servidor, não era membro dos grupos sudo ou admin , portanto command-not-found não sabia que eu poderia executar apt-get comandos com sudo . Depois de me adicionar ao grupo sudo , agora recebo o comando apt-get para executar a impressão no terminal.