O problema é o cache. O Nautilus cria um cache para miniaturas de imagens em ~ / .cache / thumbnails / . Existem vários subdiretórios nesse local.
Parece que não atualiza automaticamente o cache se a imagem mudar ou, como no caso da sua pergunta, houver uma nova imagem em um arquivo. Você pode verificar isso copiando seus arquivos para um novo local e você verá que o Nautilus exibirá a imagem na nova capa do álbum da música no novo local, mas não no local antigo.
Copie rapidamente um arquivo ou uma pasta para a área de trabalho e você verá a imagem exibida corretamente.
Pode haver uma maneira diferente de atualizar o cache, mas uma delas é removê-lo com:
$ rm -r ~/.cache/thumbnails/
Em seguida, toda vez que você visitar uma pasta com sua música, o Nautilus fará a varredura das músicas e armazenará as imagens em cache. Eles serão exibidos corretamente.