Eu tive esse problema. Que dor de cabeça isso causou. Eu não tive sucesso na linha de comando, por exemplo, a sugestão de verificar o /etc/apt/sources.list apareceu vazia e o ppa-purge não foi encontrado!
Aqui está o que eu fiz:
No atualizador do software do gui, acesse a aba do software e desmarque link principal xenial
O que eu acho que ocorreu: Eu rodei o sudo apt-get install exfat -fuse exfat utils sem prefá-lo com uma atualização do apt-get primeiro e depois com uma atualização do apt-get. O sistema foi instalado recentemente e eu queria ir direto para a formatação de um cartão SD!
Eu li em algum lugar que os utilitários exfat já estão incluídos e não precisam dos passos acima.
Estou usando o Ubuntu 16.04