You could use File::Find's finddepth rather than find to do a depth-first search. That way you'll rename those file/directories at the bottom of the directory tree first,.

Hope this helps, -gjb-