Isso também aconteceu comigo usando 16.04.1 live USB pendente do Ubuntu.
A solução da uncledave não funcionou no começo, mas, como sugerido, mudar os direitos foi a solução final.
Então eu encontrei answer # 11 de daniel-gimpelevich para o bug 1601971
Os seguintes comandos me ajudaram a reparar apt-get update
sudo chmod -R a+rX,u+w /var/cache/app-info/xapian/default
Como eu acho que 755 é a máscara certa? A diferença entre
ls -ld /var/cache/app-info/xapian
drwxr-xr-x 1 root root 4096 Nov 19 20:35 /var/cache/app-info/xapian/
e
ls -ld /var/cache/app-info/xapian/default
drw-r--r-- 2 root root 4096 Jul 19 20:54 /var/cache/app-info/xapian/default
Após esta atualização do apt-get ser executada corretamente.
sudo apt-get update
Hit:1 http://archive.ubuntu.com/ubuntu xenial InRelease
Get:2 http://security.ubuntu.com/ubuntu xenial-security InRelease [94.5 kB]
Get:3 http://archive.ubuntu.com/ubuntu xenial-updates InRelease [95.7 kB]
Fetched 190 kB in 0s (312 kB/s)
Reading package lists... Done
Note1 A atualização de um pendrive persistente ao vivo desta forma não é sugerida, pois isso causará problemas se muitos pacotes forem instalados / atualizados.
Note2 É melhor instalar o Ubuntu diretamente no pendrive se você quiser usá-lo como um "canivete suíço" inicializável.