Como por apt show appstream , versão 0.10.16-1 de appstream quebra versões de gnome-software abaixo de 3.22.5-1 , e a versão de gnome-software no Xenial é 3.20.1 . Portanto, esta versão do appstream não pode ser instalada em um sistema Xenial junto com gnome-software .
A propósito, este parece ser um bom momento para lembrar que os backports devem ser instalados manualmente uma base conforme a necessidade. Embora você possa ativar a instalação automática de backports, você o faz por sua conta e risco, pois pode causar problemas como o que você está vendo agora.