Try using File::Find and doing a depth first search, its usually better practice (less error prone) to start renaming from the deepest part of the tree twords the top IMHO.

-Waswas