Bem, isso me deixou louco por cinco minutos. Mude sua declaração para:
convert $(LC_COLLATE="C" ls -w 1000) +append sprite.png
Por algum motivo, o Nautilus não segue as configurações de localidade do sistema para que as classificações fiquem fora de sincronia. Fingindo de volta ao padrão, classifica unificar.
Meu arnês de testes:
$ mkdir test && cd test
$ touch cloudy_with_heavy_rain{,_night}.png
$ ls -l
total 0
-rw-rw-r-- 1 oli oli 0 Apr 13 00:32 cloudy_with_heavy_rain_night.png
-rw-rw-r-- 1 oli oli 0 Apr 13 00:32 cloudy_with_heavy_rain.png
$ LC_COLLATE="C" ls -l
total 0
-rw-rw-r-- 1 oli oli 0 Apr 13 00:32 cloudy_with_heavy_rain.png
-rw-rw-r-- 1 oli oli 0 Apr 13 00:32 cloudy_with_heavy_rain_night.png