Estou tendo o mesmo problema no Ubuntu 17.10. Verificado org.debian.apt.policy e todas as permissões são auth_admin ou auth_admin_keep. O Synaptic e o Aptitude funcionam bem se eu iniciá-los como root.
Meu problema real, no entanto, foi que eu estava tentando instalar o software de 'software-center', que depois de alguma pesquisa que eu descobri agora é chamado de gnome-software, eu teria o mesmo erro que você listou. Depois de encontrar esta adição do policykit , que não funcionou no meu caso, mesmo depois de atualizar o nome do arquivo para corresponder ao novo software-center, eu encontrei o problema.
Este é aparentemente um bug pouco conhecido com o XFCE no Ubuntu onde ele tenta use o policykit-1 em vez do policykit-1-gnome. Mesmo rodando 'pkexec synaptic' na linha de comando falharia (como descrito no bug). A instalação do policykit-1-gnome corrigiu esse problema para mim.
Espero que isso ajude.