ctime, mtime e atime se comportam de maneira diferente (veja, por exemplo, aqui )
ctime verifica o tempo de modificação do inode (isso é alterado, por exemplo, se você copiar um arquivo mais antigo para um novo diretório ou disco (que não muda de hora))
O mtime verifica o tempo de modificação do arquivo (que, por exemplo, não é atualizado ao copiar um arquivo para outro local ou ao descompactar um arquivo de um arquivo morto, etc.)
atime verifica o tempo de acesso
Eu diria que ctime e mtime são diferentes para a estrutura de diretórios. (E ls -ltr mostra o mtime, não o ctime.)
Sua segunda tentativa (com mtime) não deveria ter mudado o mtime do dir (este comportamento seria esperado para atime) e, de fato, para mim este comando funciona para a tarefa que você descreve. Nem mesmo no caso em que você estava faltando permissões de gravação para qualquer um dos subdiretórios deve falhar (desde que você tenha permissões de gravação para o nível superior); rm, é claro, falharia se o disco fosse montado somente para leitura, mas, nesse caso, seria impossível que o comando find alterasse a hora.