that's exactly what i would do. write a perl or whatever script to figure out which directories to rename, and the script generates a shell/batch file of the rename commands. you can review this batch rename commands before actual execution. the directory paths will need to be appropriately quoted to avoid problems.
the hardest line to type correctly is: stty erase ^H