Download
The best software I know of for this particular job is called Bulk Rename Utility. The latest version 2.7.1.2 works on Windows 7, Vista, XP, 2003, 2008, 2000, NT. Also includes a full installer. There is a 32-bit and 64-bit installer available for download:
Renaming Multiple Files in Subfolders
When you open up the utility, browse to a folder e.g. your Media library or whatever you want to rename and then at the bottom check the option Subfolders
Now all files will be loaded into the preview window. Use the fieldset Repl.(3) and enter something for Replace and With and you can see a preview, very cool!
After carefully checking the preview pane, click Rename and confirm the prompt. You are then good to go! This will hopefully save you time – it sure as hell saves me a lot of it whenever I want to rename multiple files.