Aparentemente, a versão do Nautilus do Ubuntu se destina a ordenar insensíveis a maiúsculas e minúsculas, ao contrário da maioria dos padrões de aplicativos linux. Uma pesquisa no google trouxe um tópico que acredito conter sua solução: link
% bl0ck_qu0te%No seu caso, acho que você quer LC_COLLATE="C".
Também encontrei esta postagem do askubuntu relevante: Nautilus classifica a coluna Nome "misteriosamente". Como posso alterar a sequência de intercalação?