Maybe renaming the dir confuses Find, which already thinks it knows the name of the directory to go next! You rename it, but then it can't cd to the old name!

If that's the problem, do a post- rather than preorder traversal, or just note the (fully quallified) names of all the directories in a list in the find callback, and then rename them after find finishes.

—John