Você também pode anular as letras, você só precisa alterar um pouco o comando original para:
rename 's/\w+/sprintf("%05s", $&)/e' *.jpg
Basicamente, estamos apenas dizendo, substitua a primeira "palavra" (números e letras) por uma string com preenchimento zero. É muito parecido com o original, é apenas um pouco diferente. Esta versão pode funcionar para o problema original.
Você pode expandi-lo para uma correspondência .+
(para zero pad tudo ), mas talvez seja necessário manipular a extensão na parte superior.
Arnês de teste:
$ mkdir test; cd test; touch {a..d}.jpg 1.jpg
$ rename 's/\w+/sprintf("%05s", $&)/e' *.jpg
$ ls
00001.jpg 0000a.jpg 0000b.jpg 0000c.jpg 0000d.jpg