Acredito que você acertou este bug ou similar a algo assim. O status do bug diz, há uma correção para o Zesty, mas o Xenial ainda está sob a lista de afetados.
Eu experimentei o mesmo e encontrei uma possível solução alternativa. Basta fazer o downgrade do pacote plasma-discover por um tempo.
sudo apt-get install plasma-discover/xenial-updates
deve fazer o trabalho.