Não sei como (ou mesmo se) você pode recuperar o local original de todos os arquivos. Mas, pelo menos, você poderia começar a classificá-los com base no conteúdo.
Para iniciantes, rox (aka Rox-Filer) não depende de extensões de nome de arquivo para saber o tipo de arquivo (ele usa o conteúdo real do arquivo), então se você quiser um ponto e clique em navegador que abrirá os arquivos para inspeção com o aplicativo certo, independentemente do nome do arquivo, eu tentaria rox se o Nautilus não estivesse funcionando. Se o problema com o Nautilus é que o tamanho do diretório está dificultando o uso, na minha experiência o rox funciona muito bem com listas de diretórios enormes (apenas certifique-se de que a visualização esteja desativada para imagens e vídeo).
Na linha de comando, o comando file deve informar que tipo de arquivo cada um dos arquivos é (acho que é o utilitário que o rox está usando internamente). Se você tiver algum conforto com a linha de comando, você pode até mesmo fazer alguma classificação via script (ou seja, mover filmes para um diretório, arquivos de áudio para outro, etc.).
Editar
Aqui está algo que pode ser útil, eu testei isso em algumas cópias de vários arquivos sem as extensões de nome de arquivo de três letras, então eu sei que funciona. Deve ser fácil verificar a saída do arquivo para vários itens para incluir cláusulas (e, claro, você desejará alterar os diretórios de destino para tudo isso):
#!/bin/sh
mkdir -p ~/test-imgs;
mkdir -p ~/test-vids;
mkdir -p ~/test-music;
for i in $*
do
( [ -n "'file $i | grep image'" ] && mv $i ~/test-imgs ) ||
( [ -n "'file $i | grep video'" ] && mv $i ~/test-vids ) ||
( [ -n "'file $i | grep Audio'" ] && mv $i ~/test-music ) ||
( [ -n "'file $i | grep III'" ] && mv $i ~/test-music )
done