I think you have the right idea but perhaps you should consider first building a directory index using file find and then renaming everything based on that.

That way File::Find cannot get confused and you have a record of what you changed them from as well.

Its only an idea though (hey its Saturday night and my 3rd can of beer :) )