У вас есть многопользовательский репо? Он появляется там в моей xenial системе.
Вот результат работы apt-cache policy ubuntu-restricted-extras:
ubuntu-restricted-extras:
Installed: (none)
Candidate: 65
Version table:
65 500
500 http://archive.ubuntu.com/ubuntu xenial/multiverse i386 Packages