Regarding FileWrangler speed....
Here are some time tests I just ran. Given a folder with two subfolders, themselves with two subfolders each, and a total file quantity of 50 files (some of which are RTFD documents), renaming was near instantaneous. By duplicating files and subfolders, I created a folder with six subfolders, themselves with four to six subfolders each, and a total quantity of almost 1,000 files. Renaming of all documents took about 10-15 seconds. Further reduplication of all files and subfolders, creating a complex folder heirarchy and a total of 5,000 files took 1 minute 50 seconds to rename all files.
These tests were run on a PowerBook G4 running 10.4.1 at 1.5GHz and 2GB of RAM. Your mileage may vary. I don't know if these speeds are slower than expected; they seem fairly snappy to me (especially given how long it would take to do manually). Perhaps the current lack of a progress indicator makes FileWrangler feel slower than it really is?